[leetCode]212. 单词搜索 II

题目

https://leetcode-cn.com/problems/word-search-ii/

字典树

思路:

使用深度优先搜索，遍历以各个字符开头的字符串，如果字符串存在于words列表中则加入答案。可以发现如果字符串的前缀不存在于字符串列表中，那么就不用继续搜索了，因此可以使用字典树进行优化。

class Solution {

    private List<String> ans = new ArrayList<>();
    private int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int m;
    private int n;
    private Trie trie;
    
    public List<String> findWords(char[][] board, String[] words) {
        if (board.length == 0 || board[0].length == 0) return ans;
        m = board.length;
        n = board[0].length;
        trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        boolean[][] seen = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, trie.root, seen);
            }
        }
        return ans;
    }

    private void dfs(char[][] board, int x, int y, TrieNode node, boolean[][] seen) {
        if (node.isWord) {
            if (!ans.contains(node.s)) {
                ans.add(node.s);
            }
        }

        if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y]) {
            int now = board[x][y] - 'a';
            if (node.children[now] != null) {
                for (int[] dir : dirs) {
                    int nx = x + dir[0]; 
                    int ny = y + dir[1];
                    seen[x][y] = true;
                    dfs(board, nx, ny, node.children[now], seen);
                    seen[x][y] = false;
                }
            }
        }
    }

    class TrieNode {
        String s;
        TrieNode[] children;
        boolean isWord;
        TrieNode () {
            children = new TrieNode[26];
            isWord = false;
            s = "";
        }
    }

    class Trie {
        private TrieNode root;
        public Trie () {
            root = new TrieNode();
        }

        public void insert(String word) {
            TrieNode cur = root;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if (cur.children[idx] == null) {
                    TrieNode next = new TrieNode();
                    cur.children[idx] = next;
                }
                cur = cur.children[idx];
            }
            cur.isWord = true;
            cur.s = word;
        }
    }
}