212. Word Search II

Version #1 Trie Structure + DFS with pruning by prefix checking
23.30% 
没有优化过的版本
每一次从root开始搜索
改进方法是， 在每一个TrieNode里面不存isWord而是存当前的word
然后不用StringBuilder了，每一次不从root开始search, 而是curr = curr.children[temp -'a']这样
有空再实现一下

class TrieNode {
    public boolean isWord;
    public TrieNode[] children;
    public TrieNode() {
        children = new TrieNode[26];
    }
}

public class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        ArrayList<String> result = new ArrayList<>();
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0 || words.length == 0) return result;
        TrieNode root = new TrieNode();
        buildTrie(root, words);
        int rows = board.length, cols = board[0].length;
        StringBuilder path = new StringBuilder();
        //Iterate to decide the start character
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                dfs(board, x, y, path, root, result);
            }
        }
        return result;
    }
     private int[] dx = {1, 0, -1, 0};
    private int[] dy = {0, 1, 0, -1};
    private boolean isValid(char[][] board, int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] != 0;
    }
    private void dfs(char[][] board, int x, int y, StringBuilder path, TrieNode root, ArrayList<String> result) {
        path.append(board[x][y]);
        String str = path.toString();
        //System.out.println(str + " " + prefix(root, str));
        if (find(root, str)) {
            result.add(str);
        } else if (!prefix(root, str)) {
            path.deleteCharAt(path.length() - 1);
            return;
        }
        char temp = board[x][y];
        //marked as visited
        board[x][y] = 0;
        for (int i = 0; i < 4; i++) {
            //TODO
            if (isValid(board, x + dx[i], y + dy[i])) {
                dfs(board, x + dx[i], y + dy[i], path, root, result);
            }
        }
        //backtracking
        path.deleteCharAt(path.length() - 1);
        board[x][y] = temp;
    }
 
    private void buildTrie(TrieNode root, String[] words) {
        TrieNode curr;
        int index;
        for (String word : words) {
            curr = root;
            for (int i = 0; i < word.length(); i++) {
                index = word.charAt(i) - 'a';
                if (curr.children[index] == null) curr.children[index] = new TrieNode();
                curr = curr.children[index];
            }
            curr.isWord = true;
        }
    }
    private boolean find(TrieNode root, String word) {
        TrieNode curr = root;
        int index;
        for (int i = 0; i < word.length(); i++) {
            index = word.charAt(i) - 'a';
            if (curr.children[index] == null) return false;
            curr = curr.children[index];
        }
        //Delete the word if found
        if (curr.isWord) {
            curr.isWord = false;
            return true;
        }
        return false;
    }
    private boolean prefix(TrieNode root, String prefix) {
        TrieNode curr = root;
        int index;
        for (int i = 0; i < prefix.length(); i++) {
            index = prefix.charAt(i) - 'a';
            if (curr.children[index] == null) return false;
            curr = curr.children[index];
        }
        return true;
    }
}