摘要：我們可以先用待查單詞建立一個字典樹，這樣我們在從矩陣中某個點開始深度優先搜索時，可以直接用字典樹判斷當前組成的字符串是否是某個單詞的前綴。字典樹同樣也提供接口，所以同樣可以用于判斷是否已經搜索到這個詞了。

Given a 2D board and a word, find if the word exists in the grid.
The word can 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.
For example, Given board =
[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false.

時間 O(N^2) 空間 O(N)

基本思路很簡單，對矩陣里每個點都進行一次深度優先搜索，看它能夠產生一個路徑和所給的字符串是一樣的。重點在如何優化搜索，避免不必要的計算。比如我們一個方向的搜索中已經發現了這個詞，那我們就不用再搜索。另外，為了避免循環搜索，我們還要將本輪深度優先搜索中搜索過的數字變一下，等遞歸回來之后再變回來。實現這個特性最簡單的方法就是異或上一個特定數，然后再異或回來。

public class Solution {
    public boolean exist(char[][] board, String word) {
        if(board.length == 0) return false;
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                // 從i,j點作為起點開始搜索
                boolean isExisted = search(board, i, j, word, 0);
                if(isExisted) return true;
            }
        }
        return false;
    }
    
    private boolean search(char[][] board, int i, int j, String word, int idx){
        if(idx >= word.length()) return true;
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(idx)) return false;
        // 將已經搜索過的字母標記一下，防止循環。只要變成另外一個字符，就不會再有循環了。
        board[i][j] ^= 255;
        boolean res = search(board, i-1, j, word, idx+1) || search(board, i+1, j, word, idx+1) || search(board, i, j-1, word, idx+1) || search(board, i, j+1, word, idx+1);
        // 再次異或255就能恢復成原來的字母
        board[i][j] ^= 255;
        return res;
    }
}

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.
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"].

時間 O(N^2logN) 空間 O(N)

如果還像一中那樣，對每個詞進行一遍Word Search I，那復雜度就太高了。我們可以先用待查單詞建立一個字典樹，這樣我們在從矩陣中某個點開始深度優先搜索時，可以直接用字典樹判斷當前組成的字符串是否是某個單詞的前綴。如果是某個單詞的前綴，再繼續搜索下去。字典樹同樣也提供search接口，所以同樣可以用于判斷是否已經搜索到這個詞了。

因為結果中不能有重復，我們可以在加入結果前先判斷是否已經加過該結果，也可以稍微修改一下字典樹的search方法，使得每次我們搜索到一個單詞時，將其isEnd的標記置為false，這樣下次就不會搜索到這個詞了。

public class Solution {
    
    List res;
    Trie trie;
    
    public List findWords(char[][] board, String[] words) {
        res = new LinkedList();
        trie = new Trie();
        // 構建字典樹
        for(String word : words){
            trie.insert(word);
        }
        // 深度優先搜索
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                helper(board, String.valueOf(board[i][j]), i, j);
            }
        }
        return res;
    }
    
    private void helper(char[][] board, String tmp, int i, int j){
        // 如果字典樹中存在該字符串，說明找到了單詞
        if(trie.search(tmp)){
            if(!res.contains(tmp)) res.add(tmp);
        }
        // 為了防止循環，將當前字母改變一下
        board[i][j] ^= 255;
        // 對四個方向搜索，如果當前字符串是前綴就繼續搜索
        if(j < board[0].length - 1){
            String next = tmp + board[i][j+1];
            if(trie.startsWith(next)) helper(board, next, i, j + 1);
        }
        if(i > 0){
            String next = tmp + board[i-1][j];
            if(trie.startsWith(next)) helper(board, next, i - 1, j);
        }
        if(i < board.length - 1){
            String next = tmp + board[i+1][j];
            if(trie.startsWith(next)) helper(board, next, i + 1, j);
        }
        if(j > 0){
            String next = tmp + board[i][j-1];
            if(trie.startsWith(next)) helper(board, next, i, j - 1);
        }
        board[i][j] ^= 255;
    }
    
    // 字典樹的節點
    public class TrieNode {
        Character c;
        HashMap children;
        boolean isEnd;
        public TrieNode(char c){
            this.c = c;
            this.isEnd = false;
            this.children = new HashMap();
        }
    }
    
    // 字典樹
    public class Trie {
        TrieNode root;
        
        public Trie(){
            this.root = new TrieNode("r");
        }
        
        public void insert(String str){
            TrieNode curr = root, next = null;
            int idx = 0;
            for(int i = 0; i < str.length(); i++){
                next = curr.children.get(str.charAt(i));
                if(next == null){
                    next = new TrieNode(str.charAt(i));
                }
                if(i == str.length() - 1){
                    next.isEnd = true;
                }
                curr.children.put(str.charAt(i), next);
                curr = next;
            }
        }
        
        public boolean search(String str){
            TrieNode res = searchNode(str);
            return res != null && res.isEnd ? true : false;
        }
        
        public boolean startsWith(String str){
            TrieNode res = searchNode(str);
            return res == null ? false : true;
        }
        
        private TrieNode searchNode(String str){
            TrieNode curr = root, next = null;
            for(int i = 0; i < str.length(); i++){
                next = curr.children.get(str.charAt(i));
                if(next == null){
                    return null;
                }
                curr = next;
            }
            return next;
        }
    }
}