212. Word Search II

Description

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:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]

Output:["eat","oath"]

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Hint:

• You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?
• If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: Implement Trie (Prefix Tree) first.

Solution

Trie + DFS, time O((x + m * n) * y), space O(xy)

The time complexity is

• inserting into trie: O(words.length * max word length)
• backtracking: O(board.length * board[0].length * max word length)
• total: O((words.length + board.length * board[0].length) * max word length)

很有意思的一道题。想想看在"Word Search"中是怎么做的？遍历board中的每个位置，从它开始，看能不能匹配word。

把思路扩展到这道题上。如果每次只找一个word，总的时间消耗就太大了，而且也没有memo，对于后续的查找没好处。我们应该对一组words进行统一查找，如果遇到一个pos，对应的char不匹配任何一个word，这时候就应该prune了。

所以我们用Trie来表达所有words，然后对于board中的每一个位置，用DFS去匹配Trie。

下面的代码中还有很多巧思，比如：

• 给定board中只含有lowercase letters，可以用一个特殊字符'#'取代visited[][]
• 考虑words中可能出现重复word！怎么避免呢，用HashSet？呵呵看代码吧
• 以往Trie中保存boolean isWord，如果需要返回word则需要保存path中经过的字符。这么做麻烦，不妨在build trie时就把String word存入对应的Trie中去。

class Solution {
    public static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public List<String> findWords(char[][] board, String[] words) {
        if (board == null || board.length == 0 || board[0].length == 0
           || words == null || words.length == 0) {
            return Collections.EMPTY_LIST;
        }
        
        Trie root = new Trie();
        for (String word : words) {
            buildTrie(root, word);
        }

        List<String> res = new ArrayList<>();
        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;
    }
    
    public void dfs(char[][] board, int i, int j, Trie root, List<String> res) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return;
        }
        
        char c = board[i][j];
        if (c == '#' || root.children[c - 'a'] == null) {
            return;
        }
        
        board[i][j] = '#';      // mark visited
        root = root.children[c - 'a'];
        if (root.word != null) {
            res.add(root.word);     // found a word
            root.word = null;       // avoid duplicate
        }
        
        for (int[] d : DIRECTIONS) {
            dfs(board, i + d[0], j + d[1], root, res);
        }
        
        board[i][j] = c;    // backtracking
    }
    
    public void buildTrie(Trie root, String word) {
        for (int i = 0; i < word.length(); ++i) {
            int j = word.charAt(i) - 'a';
            if (root.children[j] == null) {
                root.children[j] = new Trie();
            }
            root = root.children[j];
        }
        
        root.word = word;   // set word
    }
    
    class Trie {
        Trie[] children;
        String word;
        
        public Trie() {
            children = new Trie[26];
        }
    }
}