My simple and clean Java code using DFS and Trie


  • 85
    L

    Compared with Word Search, I make my DFS with a tire but a word. The Trie is formed by all the words in given words. Then during the DFS, for each current formed word, I check if it is in the Trie.

    public class Solution {
        Set<String> res = new HashSet<String>();
        
        public List<String> findWords(char[][] board, String[] words) {
            Trie trie = new Trie();
            for (String word : words) {
                trie.insert(word);
            }
            
            int m = board.length;
            int n = board[0].length;
            boolean[][] visited = new boolean[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    dfs(board, visited, "", i, j, trie);
                }
            }
            
            return new ArrayList<String>(res);
        }
        
        public void dfs(char[][] board, boolean[][] visited, String str, int x, int y, Trie trie) {
            if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) return;
            if (visited[x][y]) return;
            
            str += board[x][y];
            if (!trie.startsWith(str)) return;
            
            if (trie.search(str)) {
                res.add(str);
            }
            
            visited[x][y] = true;
            dfs(board, visited, str, x - 1, y, trie);
            dfs(board, visited, str, x + 1, y, trie);
            dfs(board, visited, str, x, y - 1, trie);
            dfs(board, visited, str, x, y + 1, trie);
            visited[x][y] = false;
        }
    }
    

  • 4
    L

    Here is my Trie implement:

    class TrieNode {
        public TrieNode[] children = new TrieNode[26];
        public String item = "";
        
        // Initialize your data structure here.
        public TrieNode() {
        }
    }
    
    class Trie {
        private TrieNode root;
    
        public Trie() {
            root = new TrieNode();
        }
    
        // Inserts a word into the trie.
        public void insert(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (node.children[c - 'a'] == null) {
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            node.item = word;
        }
    
        // Returns if the word is in the trie.
        public boolean search(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (node.children[c - 'a'] == null) return false;
                node = node.children[c - 'a'];
            }
            return node.item.equals(word);
        }
    
        // Returns if there is any word in the trie
        // that starts with the given prefix.
        public boolean startsWith(String prefix) {
            TrieNode node = root;
            for (char c : prefix.toCharArray()) {
                if (node.children[c - 'a'] == null) return false;
                node = node.children[c - 'a'];
            }
            return true;
        }
    }
    

  • 6
    P

    Clean and highly understandable code!!

    You can save the space of the visited n^2 array by recording the currently used character, and replace it with other illegal character and then replace it back again after you get out of the DFS.
    Of course, as along as the board is too huge and an assumption of what's illegal has to be in place first.

    if(board[x][y] == ' ') return;
    
    char tmp = board[x][y] ;
    board[x][y] = ' ';
    board[x][y] = tmp;
    

    Thanks for sharing again.


  • 0
    M

    Could you help analyze the time complexity of this method? I'm a little unsure about it


  • 4

    Hi, @Lnic. Before I see your comments, I even think that Java has a built-in implementation of Trie...


  • 1
    I

    There is a better way than search/startWith for str from the root every time you call dfs.


  • 0
    R

    I think for the following code snippet, you can do better to avoid repetitive calculation:

     if (!trie.startsWith(str)) return;
    
     if (trie.search(str)) {
            res.add(str);
        }
    

    You can use a dictionary to store the input words.


  • 0
    M

    I'm thinking if StringBuilder is better than String when we do dfs


  • 0
    L

    In dfs(board, visited, str, x - 1, y, trie), should not we generate a new copy of str? It seems to me it should be dfs(board, visited, new String(str), x - 1, y, trie). Could anybody help me to understand it? Thank you very much.


  • 0
    L

    If I add path = path.substring(0,path.length()-1); below visited[x][y] = false; It is also accepted. Could anybody tell me why?


  • 0
    M

    String is object and immutable. It is object which mean it will not create a new string. It is the reference of that string object that is passed into function. But since it is immutable, every-time you modify it, it will create a new string


  • 0
    L

    @jianchao.li.fighter
    As when I met this problem, I just had solved the problem Implement Trie (Prefix Tree) https://leetcode.com/problems/implement-trie-prefix-tree/. Then I thought the idea that using Trie.


  • 0
    L

    @iambright Like HashSet?


  • 0
    L

    @marshallou is right. str is an reference, every time you change it, str refers another String.


  • 0
    L

    Thank you for your explanation, but I still did not get it. When we run dfs(board, visited, str, x - 1, y, trie); the String referred by str has been changed. dfs(board, visited, str, x + 1, y, trie); will get a changed copy of str. What mistake did I make here?


  • 0
    M

    I do not understand your question. It seems you are right. But try to search more about "java string" "immutable" etc to fully understand the concept. http://stackoverflow.com/questions/1552301/immutability-of-strings-in-java


  • 0
    L

    I got it. String behaves like an int. Thank you.


  • 3
    K

    Thanks for the nice and clean code!

    I just wanted to share my version of the code with a few differences:

    1. Instead of having an extra visited array, I xor used characters by 256. This works in situations where the types of characters we search for is constrained to alphabets.
    2. I validate the indexes before making recursive calls, which can decrease the number of recursive calls we make. It could potentially be slightly faster because of the overhead of making recursive calls.

    public class Solution {
        public List<String> findWords(char[][] board, String[] words) {
            Trie trie = new Trie();
            for(String word : words) trie.insert(word);
            HashSet<String> res = new HashSet<String>();
            for(int i = 0; i < board.length; i++) {
                for(int j = 0; j < board[0].length; j++) {
                    if(trie.startsWith(board[i][j]+"")) {
                        String cur = board[i][j]+"";
                        board[i][j] ^= 256;
                        dfs(trie, res, board, i, j, cur);
                        board[i][j] ^= 256;
                    }
                }
            }
            return new LinkedList<String>(res);
        }
        
        int[][] diff = new int[][]{{0,1,0,-1},{1,0,-1,0}};
        public void dfs(Trie trie, HashSet<String> res, char[][] board, int i, int j, String cur) {
            if(trie.search(cur)) res.add(cur);
            for(int x = 0; x < diff[0].length; x++) {
                int newR = i + diff[0][x];
                int newC = j + diff[1][x];
                if(newR < 0 || newR >= board.length || newC < 0 || newC >= board[0].length 
                   || board[newR][newC] < 'a' || board[newR][newC] > 'z' || !trie.startsWith(cur + board[newR][newC]))
                   continue;
                String newCur = cur + board[newR][newC];
                board[newR][newC] ^= 256;
                dfs(trie, res, board, newR, newC, newCur);
                board[newR][newC] ^= 256;
            }
        }
        
        class TrieNode {
            TrieNode[] branch;
            boolean isWord;
            // Initialize your data structure here.
            public TrieNode() {
                 branch = new TrieNode[26];
            }
        }
    
        public class Trie {
            private TrieNode root;
        
            public Trie() {
                root = new TrieNode();
            }
        
            // Inserts a word into the trie.
            public void insert(String word) {
                TrieNode cur = root;
                for(int i = 0; i < word.length(); i++) {
                    char c = word.charAt(i);
                    if(cur.branch[c-'a'] == null) cur.branch[c-'a'] = new TrieNode();
                    cur = cur.branch[c-'a'];
                }
                cur.isWord = true;
            }
        
            // Returns if the word is in the trie.
            public boolean search(String word) {
                TrieNode cur = root;
                for(int i = 0; i < word.length(); i++) {
                    char c = word.charAt(i);
                    if(cur.branch[c-'a'] == null) return false;
                    cur = cur.branch[c-'a'];
                }
                return cur.isWord == true;
            }
        
            // Returns if there is any word in the trie
            // that starts with the given prefix.
            public boolean startsWith(String prefix) {
                TrieNode cur = root;
                for(int i = 0; i < prefix.length(); i++) {
                    char c = prefix.charAt(i);
                    if(cur.branch[c-'a'] == null) return false;
                    cur = cur.branch[c-'a'];
                }
                return true;
            }
        }
    }

  • 0
    M

    How could we optimize this step using a dict? I'm thinking this step is doing extra and repetitive calculation, but not sure what's the best way to avoid this.


  • 3

    Thanks for sharing this neat solution! Code can be optimized from 59ms to 15ms.

    Check it out!


Log in to reply
 

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