425. 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:

• There are at least 1 and at most 1000 words.
• All words will have the exact same length.
• Word length is at least 1 and at most 5.
• 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).

一刷
题解：给定一堆长度相同的单词，从中选出一些构成方阵，要求方阵依对角线对称。求出所有可能的方阵。

用trie+backtracking
从对角线的右上角开始，每行从array[row, row]开始， 向右增加。
对于array[row, col] 要等于array[col, row], 且对于第row行，和第col行，该前缀都要存在。
于是DFS往下进行的条件是，假设rows是存放trie树的node数组。rows[0]表示第0行的进行情况。例如area, “are”，那么rows[0]在“are”这里。
要同时满足rows[row].nodes[I]和rows[col].nodes[I]存在。否则backtracking.

public class Solution {
    class Node{
        Node[] nodes;
        String word;
        Node(){
            this.nodes = new Node[26];
            this.word = null;
        }
    }
    void add(Node root, String word){
        Node node = root;
        for (char c : word.toCharArray() ) {
            int idx = c-'a';
            if (node.nodes[idx] == null) node.nodes[idx] = new Node();
            node = node.nodes[idx];
        }
        node.word = word;
    }
    void helper(int row, int col, int len, Node[] rows, List<List<String>> ret) {
        if ( (col == row) && (row == len) ) { // last char
            List<String> res = new ArrayList<String>();
            for (int i=0; i<len; i++) {
                res.add(new String(rows[i].word) );
            }
            ret.add( res );
        } else { // from left to right and then go down to the next row
            if ( col < len  ) { // left to right first
                Node pre_row = rows[row];
                Node pre_col = rows[col];
                for (int i=0; i<26; i++) { // find all the possible next char
                    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;
                    }
                }
            } else { // reach the end of column, go to the next row
                helper(row+1, row+1, len, rows, ret);
            }
        }
    }
    public List<List<String>> wordSquares(String[] words) {
        List<List<String>> ret = new ArrayList();
        if (words==null || words.length==0) return ret;
        Node root = new Node();
        int len = words[0].length();
        for (String word: words) add(root, word);
        Node[] rows = new Node[len];
        for (int i=0; i<len; i++) rows[i]=root;
        helper(0, 0, len, rows, ret);
        return ret;
    }
}