DFS+ Trie Java for Your reference


  • 0
    H
    public class Solution {
        class TrieNode{
            boolean isWord;
            TrieNode[] child;
            public TrieNode(){
                isWord = false;
                child = new TrieNode[26];
            }
            
        }
        TrieNode root = new TrieNode();
        
        private void addToTrie(String[] words){
            for(String word: words){
                TrieNode node = root;
                for(int i=0; i< word.length(); i++){
                    char c = word.charAt(i);
                    if(node.child[c-'a']==null){
                        node.child[c-'a'] = new TrieNode();
                    }
                    node = node.child[c-'a'];
                }
                node.isWord = true;
            }
        }
        public List<String> findWords(char[][] board, String[] words) {
            List<String> res = new ArrayList<String>();
            if(board== null || words == null){
                return res;
            }
            addToTrie(words);
            StringBuilder sb = new StringBuilder();
            for(int i=0; i< board.length; i++){
                for(int j=0; j< board[0].length; j++){
                    DFSHelper(res, board, i, j, sb, root);
                }
            }
            return res;
        }
        private void DFSHelper(List<String> res, char[][] board, int i, int j, StringBuilder sb, TrieNode root){
            if(i>= board.length || i<0 || j>= board[0].length || j<0){
                return;
            }
            char c = board[i][j];
            if(c == '#' || root.child[c-'a']== null){
                return ;
            }
            root = root.child[c-'a'];
            sb.append(c);
            if(root.isWord){
                res.add(sb.toString());
                root.isWord = false;
                
            }
            board[i][j] = '#';
            
            DFSHelper(res, board, i+1, j, sb, root);
            DFSHelper(res, board, i-1, j, sb,root);
            DFSHelper(res, board, i, j+1, sb,root);
            DFSHelper(res, board, i, j-1, sb,root);
            board[i][j] = c;
            sb.setLength(sb.length()-1);
            
        }
    }
    

Log in to reply
 

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