# 212 Word Search II

找字遊戲。

給一個board，還有一個字典，找board裡面有哪些字典的字，

同一個字不可以用重複的element

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

一開始想用dfs解，看字典裡的每個字可不可以在board裡面找到，

很不幸的time limit exceeded。

看了別人的解法，#208的Trie加dfs就可以過了。

Concept:

先把字典裡的字存成字典樹，再跑過board裡的每個element，

算出每個element可能形成的string，

再一一檢查這些string是否存在字典樹中，

若是，就存到result。

Pseudocode:

Main:
    create a Trie for words
    create a Set res to save answers
    for each element in board,
        run dfs to find all possible string and check if they are in trie
    return new ArrayList(res)

dfs:
    input: index of current element, string, trie, visited
    check if index is in boundary
    append current element to string
    if trie.startswith(string) can't be found, return
    if trie.search(string) exists
        put string in res
    visited[index] = true
    run dfs for 4 neighbors
    visited[index] = false

Code:

public class Solution {
    Set<String> res = new HashSet<>();
    public List<String> findWords(char[][] board, String[] words) {

        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        Trie trie = new Trie();
        for(String w : words){
            trie.insert(w);
        }
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                dfs(board, i, j,"", trie, visited);
            }
        }
        return new ArrayList<String>(res);
    }

    void dfs(char[][] board, int x, int y, String str, Trie trie, boolean[][] visited){
        int m = board.length;
        int n = board[0].length;
        if(x<0 || x>=m || y<0 || y>=n)  return;
        if (visited[x][y]) return;
        str += board[x][y];
        if(!trie.startsWith(str))   return;
        if(trie.search(str)){
            res.add(str);
        }
        visited[x][y] = true;
        dfs(board,x-1,y,str,trie,visited);
        dfs(board,x+1,y,str,trie,visited);
        dfs(board,x,y-1,str,trie,visited);
        dfs(board,x,y+1,str,trie,visited);
        visited[x][y] = false;
    }
}
class TrieNode {
    public char val;
    public boolean isWord; 
    public TrieNode[] children = new TrieNode[26];
    public TrieNode() {}
    TrieNode(char c){
        TrieNode node = new TrieNode();
        node.val = c;
    }
}

class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
        root.val = ' ';
    }

    public void insert(String word) {
        TrieNode ws = root;
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(ws.children[c - 'a'] == null){
                ws.children[c - 'a'] = new TrieNode(c);
            }
            ws = ws.children[c - 'a'];
        }
        ws.isWord = true;
    }

    public boolean search(String word) {
        TrieNode ws = root; 
        for(int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            if(ws.children[c - 'a'] == null) return false;
            ws = ws.children[c - 'a'];
        }
        return ws.isWord;
    }

    public boolean startsWith(String prefix) {
        TrieNode ws = root; 
        for(int i = 0; i < prefix.length(); i++){
            char c = prefix.charAt(i);
            if(ws.children[c - 'a'] == null) return false;
            ws = ws.children[c - 'a'];
        }
        return true;
    }
}