Share my simple java solution


  • 0
    Z
    public class Solution {
        
        class TrieNode {
            TrieNode[] children;
            boolean flag;
            public TrieNode() {
                children = new TrieNode[26];
                flag = false;
            }
        }
        private TrieNode root = new TrieNode();;
        
        public void insert(String word) {
            TrieNode cur = root;
            for(int i=0;i<word.length();i++) {
                int index = word.charAt(i) - 'a';
                if(cur.children[index] == null) {
                    cur.children[index] = new TrieNode();
                }
                cur = cur.children[index];
            }
            cur.flag = true;
        }
        public List<String> findWords(char[][] board, String[] words) {
            List<String> res = new ArrayList<String>();
            if(board.length == 0 ) return res;
            for(String word : words) insert(word);
            HashSet<String> set = new HashSet<String>();
            for(int i=0;i<board.length;i++) {
                for(int j=0;j<board[0].length;j++) {
                    DFS(board,i,j,"",root,set);
                }
            }
            for(String s:set) res.add(s);
            return res;
        }
        
        public void DFS(char[][] board, int i, int j, String word, TrieNode cur,HashSet<String> res) {
            if(cur == null) return ;
            if(cur.flag) res.add(word);
            if(i <0 || j<0 || i>= board.length || j>= board[0].length ) return ;
            
            for(int k=0;k<26;k++) {
                if(k == board[i][j] - 'a') {
                    String next = word + board[i][j];
                    board[i][j] ^= 256;
                    DFS(board,i+1,j,next,cur.children[k],res);
                    DFS(board,i-1,j,next,cur.children[k],res);
                    DFS(board,i,j+1,next,cur.children[k],res);
                    DFS(board,i,j-1,next,cur.children[k],res);
                    board[i][j] ^= 256;
                }
            }
            
        }
    }
    

Log in to reply
 

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