Java Easy Understand Solution With Trie


  • 0
    Y
    public class Solution {
        class Trie{
            boolean end = false;
            char ch;
            Trie[] child;
            public Trie(char ch){
                this.ch = ch;
                child = new Trie[26];
            }
        }
        
        public List<String> findWords(char[][] board, String[] words) {
            Trie root = new Trie('0');
    
            for(String s: words){
                Trie node = root;
                for(char ch: s.toCharArray()){
                    if(node.child[ch - 'a'] == null)
                        node.child[ch - 'a'] = new Trie(ch);
                    node = node.child[ch - 'a'];
                }
                node.end = true;
            }
            List<String> res = new ArrayList<String>();
            for(int i = 0; i < board.length; i++){
                for(int j = 0; j < board[0].length; j++){
                    getWords(board, words, res, i, j, root, new StringBuilder());
                }
            }
            return res;
        }
        
        public void getWords(char[][] board, String[] words, List<String> res, int x, int y, Trie node, StringBuilder sb){
            if(x < 0 || y < 0 || x >= board.length || y >= board[x].length)
                return;
            if(board[x][y] == '0' || node.child[board[x][y] - 'a'] == null || node.child[board[x][y] - 'a'].ch != board[x][y])
                return;
            char tmp = board[x][y];
            sb.append(tmp);
            if(node.child[tmp - 'a'].end == true && !res.contains(sb.toString()))
                res.add(sb.toString());
            board[x][y] = '0';
            getWords(board, words, res, x + 1, y, node.child[tmp - 'a'], sb);
            getWords(board, words, res, x - 1, y, node.child[tmp - 'a'], sb);
            getWords(board, words, res, x, y + 1, node.child[tmp - 'a'], sb);
            getWords(board, words, res, x, y - 1, node.child[tmp - 'a'], sb);
            board[x][y] = tmp;
            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.