Leetcode - Word Search II

iven 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.

For example,
Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
Return ["eat","oath"].

[分析] 直接的思路是调用Word Search的方法判断输入数组中的各个单词是否在board中，这种方法是低效的。网上ljiabin 同学的博客给出了一个较好的思路，使用输入单词数组构造一个Trie字典，穷搜一遍board判断哪些字符组合出现在字典中则加入到结果集中。该方法两个好处，一是仅需穷搜一遍，二是穷搜过程中可以剪枝计算，一旦当前形成的单词甚至不是Trie树的前缀则无需判断其后续递归。为避免重复，先使用Set获取结果集最后转为List。
自己实现时使用StringBuilder表示当前已形成的单词再各层递归中传递，在{{'a','b'},{'c', 'd'}},"acdb"这个case fail了好久，最后debug出来是因为每次递归后没有恢复到初始状态。递归可以更新结果，但每层递归结束切记要恢复相关状态变量为开始本次递归时的状态，想到了那首经典的诗，“我挥一挥衣袖，不带走一片云彩” O(∩_∩)O~


[ref]
ljiabin 同学的博客
http://blog.csdn.net/ljiabin/article/details/45846527

public class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        if (board == null || board.length == 0 || board[0].length == 0 
            || words == null || words.length == 0)
            return new ArrayList<String>();
        Trie dict = new Trie();
        for (int i = 0; i < words.length; i++)
            dict.insert(words[i]);
        int rows = board.length;
        int cols = board[0].length;
        Set<String> resultSet = new HashSet<String>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                dfs(board, i, j , new StringBuilder(), new boolean[rows][cols], dict, resultSet);
            }
        }
        return new ArrayList<String>(resultSet);
    }
    public void dfs(char[][] board, int i, int j, StringBuilder curr, boolean[][] used, Trie dict, Set<String> result) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || used[i][j])
            return;
        curr.append(board[i][j]);
        String currstr = curr.toString();
        if (!dict.isPrefix(currstr)) {
            curr.deleteCharAt(curr.length() - 1); //容易被忽略，恢复递归初始状态
            return;    
        }
        if (dict.search(currstr))
            result.add(currstr);
        used[i][j] = true;
        dfs(board, i, j + 1, curr, used, dict, result);
        dfs(board, i, j - 1, curr, used, dict, result);
        dfs(board, i + 1, j, curr, used, dict, result);
        dfs(board, i - 1, j, curr, used, dict, result);
        // 恢复递归初始状态
        used[i][j] = false;
        curr.deleteCharAt(curr.length() - 1);
    }
}

class TrieNode {
    TrieNode[] children;
    public static final int ALPHABET_NUM = 26;
    boolean isAWord;
    public TrieNode() {
        children = new TrieNode[ALPHABET_NUM];
    }
}

class Trie {
    public TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    public void insert(String word) {
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (p.children[idx] == null) {
                p.children[idx] = new TrieNode();
            }
            p = p.children[idx];
        }
        p.isAWord = true;
    }
    public boolean search(String word) {
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (p.children[idx] == null)
                return false;
            p = p.children[idx];
        }
        return p.isAWord;
    }
    public boolean isPrefix(String word) {
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (p.children[idx] == null)
                return false;
            p = p.children[idx];
        }
        return true;
    }
}