Given a matrix of lower alphabets and a dictionary. Find all words in the dictionary that can be found in the matrix. A word can start from any position in the matrix and go left/right/up/down to the adjacent position.

Have you met this question in a real interview?

Yes

Example

Given matrix:

doaf


agai


dcan

and dictionary:

{"dog", "dad", "dgdg", "can", "again"}

return {"dog", "dad", "can", "again"}

1. 和一类似，需要遍历所有，所以暴力的解法就是dfs每一步和dictionary里的值比较
2. 和dictionary里的值比较这一步可以化
3. 可以借助字典树来进行前缀查询
   1. 在建树时可以记录下每一层的词，一遍加入到答案集合中
   2. 在递归时也在遍历树，所以保证可以o(1)时间做查询
   3. 是要把字典内的内容建立字典树，而不是把所有可能性建立成字典树

class TrieNode {
    String word;
    TrieNode[] children = null;
    boolean hasWord;
    public TrieNode() {
        children = new TrieNode[26];
        hasWord = false;
        word = "";
    }

    public void insert(String word, int index) {
        if (word.length() == index) {
            this.hasWord = true;
            this.word = word;
            return;
        }
        int pos = word.charAt(index) - 'a';
        if (children[pos] == null) {
            children[pos] = new TrieNode();
        }
        children[pos].insert(word, index + 1);
    }

    public TrieNode find(String word, int index) {
        if (word.length() == index) {
            return this;
        }
        int pos = word.charAt(index) - 'a';
        if (children[pos] == null) {
            return null;
        }
        return children[pos].find(word, index + 1);
    }
}


class Trie {
    public TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    public void insert(String word) {
        root.insert(word, 0);
    }
}


public class Solution {
    /*
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    private int[] dx = {0,0,1,-1};
    private int[] dy = {1,-1,0,0};
    public List<String> wordSearchII(char[][] board, List<String> words) {
        // write your code here
        List<String> ans = new ArrayList<>();
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return ans;
        }

        if (words == null || words.size() == 0) {
            return ans;
        }

        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }

    //   for (String word : words) {
    //       System.out.println(root.find(word));
    //   }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                dfs(i, j, board, trie.root, ans);
            }
        }
        return ans;
    }

    public void dfs(int i, int j, 
                    char[][] board, 
                    TrieNode root, 
                    List<String> ans) {

        if (root.hasWord) {
            if (!ans.contains(root.word)) {
                ans.add(root.word);
            }
        }

        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length || board[i][j] == '#') {
            return;
        }

        // if (root.children[board[i][j] - 'a'] == null) {
        //     return;
        // }
        if (root.children[board[i][j] - 'a'] != null) {
            for (int k = 0; k < 4; k++) {
                char ori = board[i][j];
                board[i][j] = '#';
                dfs(i + dx[k], j + dy[k], board, root.children[ori - 'a'], ans);
                board[i][j] = ori;
            }
        }
    }
}