描述

给出一个由小写字母组成的矩阵和一个字典。找出所有同时在字典和矩阵中出现的单词。一个单词可以从矩阵中的任意位置开始，可以向左/右/上/下四个相邻方向移动。

样例

给出矩阵：
doaf
agai
dcan
和字典：
{"dog", "dad", "dgdg", "can", "again"}
返回 {"dog", "dad", "can", "again"}
dog:
doaf
agai
dcan
dad:
doaf
agai
dcan
can:
doaf
agai
dcan
again:
doaf
agai
dcan

挑战

使用单词查找树来实现你的算法

代码

public class Solution {
    /**
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    
    // trie 树的模板     
    class TrieNode {
        String s;
        boolean isString;
        HashMap<Character, TrieNode> subtree;
        public TrieNode() {
            // TODO Auto-generated constructor stub
            isString = false;
            subtree = new HashMap<Character, TrieNode>();
            s = "";
        }
    };
    
    // trie 树多了一个功能：在字典中完整字符串对应的最后一个字母记录着整个字符串
    class TrieTree{
        TrieNode root ;
        public TrieTree(TrieNode TrieNode) {
            root = TrieNode;
        }
        public void insert(String s) {
            TrieNode now = root;
            for (int i = 0; i < s.length(); i++) {
                if (!now.subtree.containsKey(s.charAt(i))) {
                    now.subtree.put(s.charAt(i), new TrieNode());
                }
                now  =  now.subtree.get(s.charAt(i));
            }
            now.s = s;
            now.isString  = true;
        }
        public boolean find(String s){
            TrieNode now = root;
            for (int i = 0; i < s.length(); i++) {
                if (!now.subtree.containsKey(s.charAt(i))) {
                    return false;
                }
                now  =  now.subtree.get(s.charAt(i));
            }
            return now.isString ;
        }
    };

    public int []dx = {1, 0, -1, 0};
    public int []dy = {0, 1, 0, -1};
    
    // search中root结点代表搜索当前结点对应的分支
    public void search(char[][] board, int x, int y, TrieNode root, List<String> ans) {    
        if (root.isString == true) {
            if (!ans.contains(root.s)) {
                ans.add(root.s);
            }
        }
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] == 0 || root == null) {
            return;
        }
        if (root.subtree.containsKey(board[x][y])) {
            for (int i = 0; i < 4; i++) {
                char now = board[x][y];
                board[x][y] = 0;
                search(board, x + dx[i], y + dy[i], root.subtree.get(now), ans);
                // 回溯时要还原board[x][y]的值
                board[x][y] = now;
            }
        }
    }
    
    public List<String> wordSearchII(char[][] board, List<String> words) {
        List<String> ans = new ArrayList<String>();
        
        // 新建一个 trie 树，把字典中单词全插入 trie 树
        TrieTree tree = new TrieTree(new TrieNode());
        for (String word : words) {
            tree.insert(word);
        }
        
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                search(board, i, j, tree.root, ans);
            }
        }
        return ans;
    }
}