stringRearrangement

[Marcus Aseth]

stavo provando a risolvere la sfida 33 sezione Arcade su su codefights , ecco il testo:

Given an array of equal-length strings, check if it is possible to rearrange the strings in such a way that after the rearrangement the strings at consecutive positions would differ by exactly one character.

Example

• For inputArray = ["aba", "bbb", "bab"], the output should be
  stringsRearrangement(inputArray) = false;
  
  All rearrangements don't satisfy the description condition.
  
  
• For inputArray = ["ab", "bb", "aa"], the output should be
  stringsRearrangement(inputArray) = true.
  
  Strings can be rearranged in the following way: "aa", "ab", "bb".
  Input/Output

• [time limit] 500ms (cpp)

• [input] array.string inputArray
  
  A non-empty array of strings of lowercase letters.
  
  Guaranteed constraints:
  2 ≤ inputArray.length ≤ 10,
  1 ≤ inputArray.length ≤ 15.
  
  
  [*][output] boolean

bool stringsRearrangement(vector<string> inputArray) è la funzione che viene chiamata nel codice sull'IDE del sito, percui può essere considerata la nostra "main()" in questo caso
L'ho risolta con il codice sotto (1 struct e 4 funzioni), ma mi domandavo, sapete trovare una soluzione più efficiente al problema? (e non intendo meno righe, intendo più performante)
Per chiunque abbia voglia di cimentarsi nel problema :D

struct Node {
    Node(const string& s) :data{ s } {}

    const string data;
    vector<Node*> Similar;
};

bool stringsRearrangement(vector<string> inputArray) {
    
    sort(inputArray.begin(),inputArray.end()); //optional, works without
   
    vector<Node> Nodes;
    for (auto& s : inputArray) {
        Nodes.push_back(Node(s));
    }

    LinkNodes(Nodes);
    for (auto& n : Nodes) {
        if (SimilarSortable(n, Nodes.size())) {
            return true;
        }
    }

    return false;
}

void LinkNodes(vector<Node>& nodes)
{
    for (size_t i = 0; i < nodes.size(); i++)
    {
        for (size_t j = i + 1; j < nodes.size(); j++)
        {
            auto& Current = nodes[i];
            auto& Other = nodes[j];
            if (HasOneDifferentCharacter(Current.data, Other.data))
            {
                Current.Similar.push_back(&Other);
                Other.Similar.push_back(&Current);
            }
        }
    }
}

bool SimilarSortable(Node& node, int size, set<Node*> skip = set<Node*>())
{
    skip.insert(&node);
    auto& Similars = node.Similar;
   
    //case found sequence
    if (skip.size() == size){
        return true;
    }

    //case no linked
    if (Similars.size() == 0){
        return false;
    }

    for (auto& s : Similars)
    {
        if (skip.find(s) == skip.end())
        {
            if (SimilarSortable(*s, size, skip))
            {
                return true;
            }
        }
    }

    return false;
}

bool HasOneDifferentCharacter(const string& first, const string& second)
{
    auto difference = 0;
    for (size_t i = 0; i < first.size(); i++)
    {
        if (!(first[i] == second[i]))
        {
            difference++;
        }
    }
    return (difference == 1 ? true : false);
}

// Test cases setup

int main()
{
    using Pair = pair<vector<string>, bool>;
    vector<Pair> inputArrays{
        Pair({ "aba","bbb","bab" },false),
        Pair({ "ab","bb","aa" },true),
        Pair({ "q","q"},false),
        Pair({ "zzzzab","zzzzbb","zzzzaa" },true),
        Pair({ "ab","ad","ef","eg" },false),
        Pair({ "abc","bef","bcc","bec","bbc","bdc" },true),
        Pair({ "abc","abx","axx","abc" },false),
        Pair({ "abc","abx","axx","abx","abc" },true),
        Pair({ "f","g","a","h" },true),
        Pair({ "ff","gf","af","ar","hf" },true),
        Pair({ "oh","eh","ah","po","op" },false),
        Pair({ "zzzabzczaba","zzzabzczaaa","zzzabzczabb","zzzabzczbbb" },true),
        Pair({ "zzzabzczaaa","zzzabzczaaa","zzzabzczaaa","zzzabzczaaa" },false),
        Pair({ "abc","xbc","xxc","xbc","aby","ayy","aby","azc" },false),
        Pair({ "abc","bef","bcc","bew","zew","zyw","bec","bbc","bdc" },true),
        Pair({ "abacabaabczzzzz","abacababefzzzzz","abacababcczzzzz","abacababeczzzzz","abacababbczzzzz","abacababdczzzzz" },true),
        Pair({ "abc","xbc","xxc","xbc","aby","ayy","aby" },true),
        Pair({ "abc","xbc","axc","abx" },    false)
    };

    int Case = 1;
    for (auto& arr : inputArrays) {
        cout << "Case " << Case++ << ": ";
        bool result = stringsRearrangement(arr.first);
       
        cout << boolalpha << "-> " << result << endl;
        cout << "Expected Output: " << arr.second << endl << endl;
    }
}
/code]