LeetCode 212. Word Search II

[Woodyiiiiiii]

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Note:

1. All inputs are consist of lowercase letters a-z.
2. The values of words are distinct.

---

这道题跟No.79 Word Search扩展的地方在于给了一堆单词，来返回存在的单词。当然沿用基础题的思路，用Bruce Force是可以做的。但问题在于如何判断某个生成字符串是否是单词库里的单词或者前缀来进行判断返回或者剪枝优化。这部分内容如果用迭代单词库里的单词的做法的话就会超时，所以需要使用 Trie(字典树) 结构来完成判断，达到O(N)的时间复杂度(N是要判断的字符串长度)。

注意当判断search函数确认当前字符串存在于单词库后，不要返回，因为可能会有下个单词库的单词出现一开始我没想到卡了我一会儿。

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        ArrayList<String> res = new ArrayList<>();
        int m = board.length;
        if (m == 0) return res;
        int n = board[0].length;
        boolean[][] v = new boolean[m][n];
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                dfs(board, v, i, j, trie, res, "");
            }
        }
        return res;
    }
    void dfs(char[][] board, boolean[][] v, int i, int j,
                    Trie trie, ArrayList<String> res, String s) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length
            || v[i][j]) 
            return;
        String tmp = s + board[i][j];
        if (!trie.startsWith(tmp)) {
            return;
        }
        if (trie.search(tmp) && !res.contains(tmp)) {
            res.add(new String(tmp));
        }
        v[i][j] = true;
        dfs(board, v, i - 1, j, trie, res, new String(tmp));
        dfs(board, v, i, j - 1, trie, res, new String(tmp));
        dfs(board, v, i + 1, j, trie, res, new String(tmp));
        dfs(board, v, i, j + 1, trie, res, new String(tmp));
        v[i][j] = false;
    }
}
class Trie {
    TreeNode root;
    
    class TreeNode {
        TreeNode[] nodes = new TreeNode[26];
        boolean end = false;
    }

    public Trie() {
        root = new TreeNode();
    }
    
    public void insert(String word) {
        TreeNode tmp = root;
        for (int i = 0; i < word.length(); ++i) {
            int idx = word.charAt(i) - 'a';
            if (tmp.nodes[idx] == null) {
                tmp.nodes[idx] = new TreeNode();
            }
            tmp = tmp.nodes[idx];
        }
        tmp.end = true;
    }
    
    private TreeNode searchNode(String word) {
        TreeNode tmp = root;
        for (int i = 0; i < word.length(); ++i) {
            int idx = word.charAt(i) - 'a';
            if (tmp.nodes[idx] == null) {
                return null;
            }
            tmp = tmp.nodes[idx];
        }
        return tmp;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TreeNode tmp = searchNode(word);
        return tmp == null ? false : tmp.end;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return searchNode(prefix) == null ? false : true;
    }
}

---

类似题目：

• https://leetcode.com/problems/word-search/
• https://leetcode.com/problems/implement-trie-prefix-tree/

参考资料：

• https://leetcode.com/problems/word-search-ii/
• [LeetCode] 212. Word Search II grandyang/leetcode#212