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.
public List<List<String>> wordSquares(String[] words) {
List<List<String>> result = new ArrayList<>();
int size = words[0].length();
Set<String> used = new HashSet<>();
List<String> squares = new ArrayList<>();
for (int i = 0;
i < words.length;
i++) {
used.add(words[i]);
squares.add(words[i]);
backtrack(squares, used, size, words, result);
used.remove(words[i]);
squares.remove(squares.size() - 1);
}
return result;
}
private void backtrack(List<String> squares, Set<String> used, int size, String[] words, List<List<String>> result) {
if (squares.size() == size) {
result.add(new ArrayList<>(squares));
return;
}
for (int i = 0;
i < words.length;
i++) {
if (!used.contains(words[i])) {
if (isValidWord(squares, words[i], size)) {
used.add(words[i]);
squares.add(words[i]);
backtrack(squares, used, size, words, result);
used.remove(words[i]);
squares.remove(squares.size() - 1);
}
}
}
}
private boolean isValidWord(List<String> squares, String word, int size) {
for (int i = 0;
i < size;
i++) {
StringBuilder columnWord = new StringBuilder();
for (int j = 0;
j < squares.size();
j++) {
columnWord.append(squares.get(j).charAt(i));
}
columnWord.append(word.charAt(i));
if (!Arrays.asList(words).contains(columnWord.toString())) {
return false;
}
}
return true;
}Follow-up:
How would you optimize the solution to handle a large input list of words?
