Word Squares

Given a set of words (without duplicates), find all word squares you can build from them.

A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.

b a l l
a r e a
l e a d
l a d y

Note:

1. There are at least 1 and at most 1000 words.
2. All words will have the exact same length.
3. Word length is at least 1 and at most 5.
4. Each word contains only lowercase English alphabet a-z.

Example 1:

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

Output:
[
  [ "wall",
    "area",
    "lead",
    "lady"
  ],
  [ "ball",
    "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:
["abat","baba","atan","atal"]

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

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).

Tips:

简直难。。。26^(n*n)

By considering the word squares as a symmetric matrix, my idea is to go through the top right triangular matrix in left-to-right and then down order. For example, with the case of ["area","lead","wall","lady","ball"] where length = 4, we start with 4 empty string "" "" "" "" Next, [0,0] , "a","b", "l", "w" can be placed, we start with "a" "a" "" "" "" [0,1] go right, "r" can be placed after "a", but no words start with "r" at [1,0], so this DFS ends. "ar" "" "" "" Now, start with "b" at [0,0] "b" "" "" "" We can have "ba" at [0,1] and there is a word start with "a" "ba" "a" "" "" Next "bal" "a" "l" "" Next "ball" "a" "l" "l" When finish the first row, go down to next row and start at [1,1] "ball" "ar" "l" "l" ..... so on and so forth until reaching [4,4]

Details:

if ( (rows[row].nodes[i] != null) && (rows[col].nodes[i] != null) ) { rows[row] = rows[row].nodes[i]; if (col != row) rows[col] = rows[col].nodes[i]; helper(row, col+1, len, rows, ret); rows[row] = pre_row; if (col != row) rows[col] = pre_col; } Input: ["area","lead","wall","lady","ball"] let's assume that row = 2, col= 2 and we have rows[0] = w a l l rows[1] = a r e a rows[2] = l e ? rows[3] = l a Then, we find a letter from a ~ z which after rows[2] to fill the "?" mark. This is the case of row==col. rows[2] is a Trie node currently representing prefix "le" when i=0, 'a' is the letter after this prefix. rows[2] move to lea To prevent from moving the same pointer twice, we have the condition if (col != row) Therefore, we move to the "right" by giving col+1 for the next DFS step.

Now, we have row = 2, col= 3 and rows[0] = w a l l rows[1] = a r e a rows[2] = l e a ? rows[3] = l a ? Then, we find a letter from a ~ z which after rows[2] and rows[3] to fill the "?" mark. rows[2] is a Trie node currently representing prefix "lea" rows[3] is a Trie node currently representing prefix "la" when i=3, 'd' is the letter which after these two prefixes. rows[2] move to lea'd' rows[3] move to la'd'

The last two lines are the backtracking. rows[row] = pre_row; if (col != row) rows[col] = pre_col;

Code:

public class Solution {
    class TrieNode{
        TrieNode[] children;
        String word;
        TrieNode() {
            this.children = new TrieNode[26];
            this.word = null;
        }
    }
    private void add(TrieNode root, String word) {
        TrieNode node = root;
        for (char c : word.toCharArray() ) {
            int idx = c-'a';
            if (node.children[idx] == null) node.children[idx] = new TrieNode();
            node = node.children[idx];
        }
        node.word = word;
    }
    public List<List<String>> wordSquares(String[] words) {
        List<List<String>> res = new ArrayList<>();
        if (words == null || words.length == 0) return res;
        TrieNode root = new TrieNode();
        for (String word : words) add(root, word);
        int len = words[0].length();
        TrieNode[] rows = new TrieNode[len];
        for (int i = 0; i < len; i++) rows[i] = root;
        helper(0, 0, len, rows, res);
        return res;
    }

    private void helper(int row, int col, int len, TrieNode[] rows, List<List<String>> res) {
        if (col == row && row == len) {
            List<String> curt = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                curt.add(new String(rows[i].word));
            }
            res.add(curt);
            return;
        }

        if (col < len) {
            TrieNode pre_row = rows[row];
            TrieNode pre_col = rows[col];
            for (int i = 0; i < 26; i++) {
                if (rows[row].children[i] != null && rows[col].children[i] != null) {
                    rows[row] = rows[row].children[i];
                    if (col != row) rows[col] = rows[col].children[i];
                    helper(row, col + 1, len, rows, res);
                    rows[row] = pre_row;
                    rows[col] = pre_col;
                }
            }
        } else {
            helper(row + 1, row + 1, len, rows, res);
        }
    }
}