Java DFS +TRIE 20ms solution


  • 2
    Z
    public class Solution {
    public class TrieNode {
        public String result;
        public TrieNode[] next = new TrieNode[26];
    }
    public List<String> findWords(char[][] board, String[] words) {
        // build trie
        TrieNode root = new TrieNode();
        for (int i = 0; i < words.length; i ++) {
            String word = words[i];
            TrieNode curr = root;
            for (int j = 0; j < word.length(); j ++) {
                char c = word.charAt(j);
                if (curr.next[c -'a'] == null) {
                    TrieNode newnode = new TrieNode();
                    curr.next[c - 'a'] = newnode;
                }
                curr = curr.next[c - 'a'];
            }
            curr.result = word;
        }
        int[][] visited = new int [board.length][board[0].length];
        ArrayList<String> result = new ArrayList<String>();
        for (int i = 0; i < board.length; i ++) {
            for (int j = 0; j < board[0].length; j++) {
                
                dfs(board, i, j, root, result, visited);
            }
        }
        return result;
    }
    
    private void dfs (char[][] board, int i, int j, TrieNode root, List<String> result, int[][] visited){
        if (visited[i][j] == 1) return;
        char c = board[i][j];
        if (root.next[c - 'a'] == null) return;
        if (root.next[c - 'a'].result != null && !result.contains(root.next[c - 'a'].result)) {
            result.add(root.next[c - 'a'].result);
        }
        visited[i][j] = 1;
        if (i > 0) dfs(board, i - 1, j, root.next[c-'a'], result, visited);
        if (i < board.length - 1) dfs(board, i + 1, j, root.next[c-'a'], result, visited);
        if (j > 0) dfs(board, i, j - 1, root.next[c-'a'], result, visited);
        if (j < board[0].length - 1) dfs(board, i, j + 1, root.next[c-'a'], result, visited);
        visited[i][j] = 0;
    }
    

    }


  • 0
    S

    Instead of searching for duplicates in List "result" (which takes O(n)), you can set TrieNode's result to null. Check if a node's result is null, then we add it.
    We will also need to filter out duplicate in "words", which we can do using a set.


Log in to reply
 

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