425 Word Squares

• Unfinished, current implementation:

• But the idea now is not generate the universal set of size of the word, and valid them.

• O(n^n);

vector<vector<string>> sub_perms(vector<vector<string>> &cur_list, string &word)
{
    vector<vector<string>> new_list;

    for (int i = 0; i < cur_list.size(); i++) {
        for (int j = 0; j <= cur_list[i].size(); j++) {
            vector<string> temp = cur_list[i];
            temp.insert(temp.begin() + j, word);
            new_list.push_back(temp);
        }
    }
    return new_list;
}

vector<vector<string>> generate_permutations(vector<string> &words)
{
    if (words.empty()) return vector<vector<string>>();
    vector<vector<string>> all_perms = { { words[0] } };

    for (int i = 1; i < words.size(); i++) {
        all_perms = sub_perms(all_perms, words[i]);
    }

    return all_perms;
}

bool is_word_square(vector<string> &ws)
{
    print(ws);
    for (int row = 0; row < ws.size(); row++) {
        string row_word = ws[row];
        cout << row_word; pause();
        for (int col = 0; col < ws.at(row).size(); col++) {
            cout << ws[col][row]; pause();
            if (ws[col][row] != row_word[col]) return false;
        }
    }
    return true;
}

vector<vector<string>> wordSquares(vector<string>& words) 
{
    vector<vector<string>> all_perms = generate_permutations(words);
    vector<vector<string>> valid_ws;
    for (int vec = 0; vec < all_perms.size(); vec++) {
        if (is_word_square(all_perms[vec])) 
            valid_ws.push_back(all_perms[vec]);
    }

    return valid_ws;
}


int main()
{
    vector<string> test = { "abat","baba","atan","atal" };
    print2d(wordSquares(test));

    test = { "area","lead","wall","lady","ball" };
    print2d(wordSquares(test));

    test = { "ball","area","lead","lady" };
    print2d(wordSquares(test));
}