Given a set of words(without duplicates), find allword squaresyou can build from them.

A sequence of words forms a valid word square if thekthrow 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 .

tag: backtracking, Trie

class Solution {
    private class TrieNode{
        TrieNode[] children;
        List<String> words;

        public TrieNode(){
            children = new TrieNode[26];
            words = new ArrayList<>();
        }

        public void insert(String word, int index){
            if (index == word.length()){
                return;
            }

            int pos = word.charAt(index) - 'a';
            if (children[pos] == null){
                children[pos] = new TrieNode();
            }

            children[pos].words.add(word);

            children[pos].insert(word, index + 1);
        }

        public List<String> search(String prefix, int index){
            if (index == prefix.length()){
                return words;
            }

            int pos = prefix.charAt(index) - 'a';

            if (children[pos] == null) return new ArrayList<String>();

            return children[pos].search(prefix, index + 1);
        }
    }

    public List<List<String>> wordSquares(String[] words) {
        List<List<String>> ans = new ArrayList<>();
        if (words == null || words.length == 0) return ans;

        int n = words[0].length();
        TrieNode root = new TrieNode();
        for (String word : words){
            root.insert(word, 0);
        }

        List<String> path = new ArrayList<>();
        for (String word : words){
            path.add(word);
            dfs(n, root, path, ans);
            path.remove(path.size() - 1);
        }

        return ans;
    }

    private void dfs(int len, TrieNode root, List<String> path, List<List<String>> ans){
        if (path.size() == len){
            ans.add(new ArrayList<String>(path));
            return;
        }

        StringBuilder sb = new StringBuilder();
        int index = path.size();
        for (String word : path){
            //System.out.println("path: " + path + "word from path: " + word + " path size: " + path.size());
            sb.append(word.charAt(index));
        }
        String prefix = sb.toString();

        List<String> candidates = root.search(prefix, 0);

        for (String word : candidates){
            path.add(word);
            dfs(len, root, path, ans);
            path.remove(path.size() - 1);
        }
    }
}