Word Squares

Problem Statement

In this problem, we are given an array of unique strings named words. Our goal is to construct all possible word squares using these strings. A word from the array can be repeatedly used in different word squares. The result can be presented in any order without affecting correctness.

A word square is a sequence of strings that form a square matrix where the strings must read the same horizontally (left to right) and vertically (top to bottom) along the kth row and column for all possible k, where 0 <= k < max(numRows, numColumns).

For clarity, consider the word sequence ["ball","area","lead","lady"]. This set of words forms an appropriate word square because each word can be read identically across and down, making squares of words align perfectly both horizontally and vertically.

Examples

Example 1

Input:

words = ["area","lead","wall","lady","ball"]

Output:

[["ball","area","lead","lady"],["wall","area","lead","lady"]]

Explanation:

The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Example 2

Input:

words = ["abat","baba","atan","atal"]

Output:

[["baba","abat","baba","atal"],["baba","abat","baba","atan"]]

Explanation:

The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Constraints

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 4
• All words[i] have the same length.
• words[i] consists of only lowercase English letters.
• All words[i] are unique.

Approach and Intuition

To approach this problem, let's break down the conditions and understand the concept through the examples provided:

Example Understanding

1. Example 1:
   The input list is ["area","lead","wall","lady","ball"]. Two word squares possible here are:

   [["ball","area","lead","lady"],["wall","area","lead","lady"]]

   Analyzing one square:

   ball
   area
   lead
   lady

   Here, b, a, l, l forms both the first column and the first row, and so on for other rows and columns.

2. Example 2:
   Given ["abat","baba","atan","atal"], we can generate:

   [["baba","abat","baba","atal"],["baba","abat","baba","atan"]]

   One such square would be:

   baba
   abat
   baba
   atal

   Notice how each row mirrors its respective column.

Key Observations and Steps:

1. The characters at each position across the words must lead to a valid mirror horizontally and vertically upon placement.
2. Given that all words are of the same length and are unique, but can be reused, it's ideal to use a backtracking approach:
   • Start forming the word square row by row using the words.
   • For each word added to the square, ensure it is consistent with previously added words in forming a valid square as per the kth row and column.
   • Continue exploring possible words that can complete the word square, reverting (backtracking) if a word doesn't lead to a valid solution.
3. Efficiency can be potentially improved using prefix hashing (storing words by their prefix for quick lookup), especially given the constraints where word length can go up to 4, making this manageable.

This backtracking method, augmented with effective checks for forming valid word squares, ensures that all combinations are explored without redundant calculation, adhering to the unique constraint induced by the problem definition.

Solutions

class TrieNode {
  HashMap<Character, TrieNode> descendants = new HashMap<>();
  List<Integer> indices = new ArrayList<>();
    
  public TrieNode() {}
}
    
class Solution {
  int wordLength = 0;
  String[] wordArray = null;
  TrieNode root = null;
    
  public List<List<String>> wordSquares(String[] words) {
    this.wordArray = words;
    this.wordLength = words[0].length();
    
    List<List<String>> allResults = new ArrayList<>();
    this.constructTrie(words);
    
    for (String word : words) {
      LinkedList<String> currentSquare = new LinkedList<>();
      currentSquare.addLast(word);
      this.depthFirstSearch(1, currentSquare, allResults);
    }
    return allResults;
  }
    
  protected void depthFirstSearch(int depth, LinkedList<String> currentSquare,
                              List<List<String>> allResults) {
    if (depth == wordLength) {
      allResults.add(new ArrayList<>(currentSquare));
      return;
    }
    
    StringBuilder prefixBuilder = new StringBuilder();
    for (String word : currentSquare) {
      prefixBuilder.append(word.charAt(depth));
    }
    
    for (Integer index : this.findWordsByPrefix(prefixBuilder.toString())) {
      currentSquare.addLast(this.wordArray[index]);
      this.depthFirstSearch(depth + 1, currentSquare, allResults);
      currentSquare.removeLast();
    }
  }
    
  protected void constructTrie(String[] words) {
    this.root = new TrieNode();
    
    for (int index = 0; index < words.length; ++index) {
      String word = words[index];
    
      TrieNode node = this.root;
      for (char character : word.toCharArray()) {
        if (!node.descendants.containsKey(character)) {
          TrieNode newNode = new TrieNode();
          node.descendants.put(character, newNode);
        }
        node = node.descendants.get(character);
        node.indices.add(index);
      }
    }
  }
    
  protected List<Integer> findWordsByPrefix(String prefix) {
    TrieNode node = this.root;
    for (char character : prefix.toCharArray()) {
      if (node.descendants.containsKey(character)) {
        node = node.descendants.get(character);
      } else {
        return new ArrayList<>();
      }
    }
    return node.indices;
  }
}