# 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));