425. Word Squares

class Solution {
    public List<List<String>> wordSquares(String[] words) {
        if(words == null || words.length < 1) return re;
        int n = words[0].length();
        for(String w : words) root.insert(w);
        dfs(words, new ArrayList<>());
        return re;
    }

    Trie root = new Trie();
    List<List<String>> re = new ArrayList<>();

    void dfs(String[] words, List<String> list)
    {
        // System.out.println(list);
        int n = words[0].length(), pos = list.size();
        if(pos == n)
        {
            re.add(new ArrayList<>(list));
            return;
        }
        if(pos >= words[0].length()) return;
        String prefix = prefix(list);
        Set<String> wordSet = root.getWords(prefix);
        for(String word : wordSet)
        {
            list.add(word);
            dfs(words, list);
            list.remove(pos);
        }
    }

    String prefix(List<String> list)
    {
        int pos = list.size();
        if(pos == 0) return "";
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < pos; i++) sb.append(list.get(i).charAt(pos));
        return sb.toString();
    }

    class Trie
    {
        Trie[] child = new Trie[26];
        Set<String> set = new HashSet<>();

        void insert(String str)
        {
            Trie root = this;
            for(char ch : str.toCharArray())
            {
                root.set.add(str);
                if(root.child[ch - 'a'] == null) root.child[ch - 'a'] = new Trie();
                root = root.child[ch - 'a'];
            }
            root.set.add(str);
        }

        Set<String> getWords(String prefix)
        {
            Trie root = this;
            for(char ch : prefix.toCharArray())
            {
                if(root.child[ch - 'a'] == null) return new HashSet<>();
                root = root.child[ch - 'a'];
            }
            return root.set;
        }
    }
}