Simple straight forward Java Trie + backtracking solution 38ms beat 95.39%


  • 0
    A

    "w a l l"
    "a r e a"

    "w a l l"
    "a r e a"
    "l e a d"

    "w a l l"
    "a r e a"
    "l e a d"
    "l a d y"

    public class Solution {
        class Node{
            List<String> words;
            Node[] children;
            Node(){
                words = new ArrayList<>();
                children = new Node[26];
            }
        }
        Node root;
        
        public void buildTrie(String[] words){
            this.root = new Node();
            Node node;
            for(int i = 0; i<words.length; i++){
                node = root;
                for(int j = 0; j<words[i].length(); j++){
                    int index = words[i].charAt(j)-'a';
                    if(node.children[index]==null)
                        node.children[index] = new Node();
                    node.words.add(words[i]);
                    node = node.children[index];
                }
            }
        }
        
        private void search(Node root, String[] words, List<List<String>> res, List<String> cur, int row, int col){
            if(cur.size()==words[0].length()){
                res.add(new ArrayList<>(cur));
                return;
            }
            //if prefix is matched, try every words that has this prefix
            if(row == cur.size()){
                for(int i = 0; i<root.words.size(); i++){
                    cur.add(root.words.get(i));
                    search(this.root, words, res, cur, 0, col+1);
                    cur.remove(cur.size()-1);
                }
            }
            else{
                Node node = root.children[cur.get(row).charAt(col)-'a'];
                if(node!=null)
                    search(node, words, res, cur, row+1, col);
            }
        }
        
        public List<List<String>> wordSquares(String[] words) {
            List<List<String>> res = new ArrayList<>();
            List<String> cur = new ArrayList<>();
            
            buildTrie(words);
            
            for(int i = 0; i<words.length; i++){
                cur.add(words[i]);
                search(root, words, res, cur, 0, 1);
                cur.remove(cur.size()-1);
            }
            
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.