Word Square
Given a list of words, find all possible word squares. A word square is a square grid of words where each row and column forms a word.
Constraints:
- The input list will contain at least one word and at most 10 words.
- Each word will have the same length.
- Each word will contain only lowercase English letters.
- The length of each word will be at least 1 and at most 10.
Examples:
Input: ["area", "lead", "line", "ball"]
Output: [["ball", "area", "lead", "line"]]
Explanation: The output is a list of word squares, where each word square is a 2D list of words. In this example, the word square is a 4x4 grid where each row and column forms a word.
Solutions
Backtracking
The solution uses a backtracking approach to find all possible word squares. It starts by iterating over each word in the input list and adding it to the current square. Then, it checks if the current square is valid by calling the isValidWord function. If the square is valid, it recursively calls the backtrack function to add more words to the square. If the square is not valid, it backtracks and tries a different word. The solution uses a set to keep track of used words to avoid duplicates.
vector<vector<string>> wordSquares(vector<string>& words) {
vector<vector<string>> result;
int size = words[0].size();
unordered_set<string> used;
vector<string> squares;
for (int i = 0;
i < words.size();
i++) {
used.insert(words[i]);
squares.push_back(words[i]);
backtrack(squares, used, size, words, result);
used.erase(words[i]);
squares.pop_back();
}
return result;
}
void backtrack(vector<string>& squares, unordered_set<string>& used, int size, vector<string>& words, vector<vector<string>>& result) {
if (squares.size() == size) {
result.push_back(squares);
return;
}
for (int i = 0;
i < words.size();
i++) {
if (used.find(words[i]) == used.end()) {
if (isValidWord(squares, words[i], size)) {
used.insert(words[i]);
squares.push_back(words[i]);
backtrack(squares, used, size, words, result);
used.erase(words[i]);
squares.pop_back();
}
}
}
}
bool isValidWord(vector<string>& squares, string& word, int size) {
for (int i = 0;
i < size;
i++) {
string columnWord;
for (int j = 0;
j < squares.size();
j++) {
columnWord += squares[j][i];
}
columnWord += word[i];
if (find(words.begin(), words.end(), columnWord) == words.end()) {
return false;
}
}
return true;
}Follow-up:
How would you optimize the solution to handle a large input list of words?
