212. Word Search II

LeetCode

Approach: Backtracking with Trie

Copy

class Solution { 
    class TrieNode {
        TrieNode[] next = new TrieNode[26];
        String word;
    }
    
    public TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode p = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (p.next[i] == null) p.next[i] = new TrieNode();
                p = p.next[i];
            }
            p.word = w;
        }
        return root;
    }
    
    public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res, int[][] dir) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;
        char c = board[i][j];
        if (c == '#' || p.next[c - 'a'] == null) return;
        p = p.next[c - 'a'];
        if (p.word != null) { // found one
            res.add(p.word);
            p.word = null; // de-duplicate
        }

        board[i][j] = '#';
        for(int[] d:dir){
            dfs(board, i+d[0], j+d[1], p, res, dir);
        }
        board[i][j] = c;
    }
    
    public List<String> findWords(char[][] board, String[] words) {
        int[][] dir = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
        List<String> res = new ArrayList<>();
        TrieNode root = buildTrie(words);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, res, dir);
            }
        }
        return res;
    }
}
/*
class Solution {
    class TrieNode {
        TrieNode[] next = new TrieNode[26];
        String word;
    }
    
    public TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode p = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (p.next[i] == null) p.next[i] = new TrieNode();
                p = p.next[i];
            }
            p.word = w;
        }
        return root;
    }
    
    public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
        char c = board[i][j];
        if (c == '#' || p.next[c - 'a'] == null) return;
        p = p.next[c - 'a'];
        if (p.word != null) { // found one
            res.add(p.word);
            p.word = null; // de-duplicate
        }

        board[i][j] = '#';
        if (i > 0) dfs(board, i - 1, j, p, res);
        if (j > 0) dfs(board, i, j - 1, p, res);
        if (i < board.length - 1) dfs(board, i + 1, j, p, res);
        if (j < board[0].length - 1) dfs(board, i, j + 1, p, res);
        board[i][j] = c;
    }
    
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        TrieNode root = buildTrie(words);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, res);
            }
        }
        return res;
    }
}*/

---

Approach: Backtracking

Copy

// Accepted
class Solution {
    private int[][] dir = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    private Set<String> res = new HashSet<>();

    private void dfs(char[][] board, int i, int j, String word, int pos, boolean[][] seen) {
        if (pos == word.length()) {
            res.add(word);
            return;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || seen[i][j] || board[i][j] != word.charAt(pos)) return;
        seen[i][j] = true;
        for (int[] d : dir) {
            dfs(board, i + d[0], j + d[1], word, pos + 1, seen);
        }
        seen[i][j] = false;
    }

    public List<String> findWords(char[][] board, String[] words) {
        int R = board.length, C = board[0].length;
        for (String word : words) {
            boolean[][] seen = new boolean[R][C];
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    dfs(board, i, j, word, 0, seen);
                }
            }
        }
        return new ArrayList<String>(res);
    }
}
// 	Time Limit Exceeded
/*
class Solution {
    private int[][] dir = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    private Set<String> res = new HashSet<>();

    private void dfs(char[][] board, int i, int j, String word, StringBuilder tmp, boolean[][] seen) {   
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;
        if (!seen[i][j]) {
            tmp.append(board[i][j]);
            if (tmp.toString().equals(word)) {
                res.add(word);
            }
            seen[i][j] = true;
            for (int[] d : dir) {
                int i_next = i + d[0];
                int j_next = j + d[1];
                dfs(board, i_next, j_next, word, tmp, seen);
            }
            tmp.deleteCharAt(tmp.length() - 1);
            seen[i][j] = false;
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        int R = board.length, C = board[0].length;
        for (String word : words) {
            StringBuilder tmp = new StringBuilder();
            boolean[][] seen = new boolean[R][C];
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    dfs(board, i, j, word, tmp, seen);
                }
            }
        }
        return new ArrayList<String>(res);
    }
}*/