212. Word Search II

刷
June-21-2019

Trie + word search是CS1501的作业题，当时做了1个月。
DFS + backtrack + trie，正好复习了一下dfs + backtrack
说说做错的地方：
一开始是用board[][]建字典，枚举所有可能，然后在里面搜索words，这样建树花时间太长太长了，相当于枚举出board[][]可以组成的所有单词= =。正确的方法是，通过words建树，然后在board里找，很多情况都可以直接剪枝。
第二个错的地方是，Trie完全没吊用。。记住Root就行，所以一个class足够。然后isLetter其实是说isWord，刚才几个题也写错了，不知道在想什么。
第三个是，DFS是下去的那层来判断是否找到word，要在边界check之前完成；
第四个是，不一定非要boolean[][]可以通过+26变大写之类的来代表visited
另外：
上下左右用了个小trick
字母类还是Node[26]好一些
DFS回溯没做错= =不容易

class Solution {
                                             // 1  0  -1  0
    private static final int[] MOVE = new int[]{0, 1, 0, -1, 0};
    
    public class Node {
        Character letter;
        boolean isLetter;
        Node[] nextLevel;
        
        public Node(Character c) {
            this.letter = c;
            this.isLetter = false;
            nextLevel = new Node[26];
        }
    }
    
    public class Trie {
        Node root;
        
        public Trie() {
            root = new Node(null);
        }
        
        public void add(String word) {
            Node temp = root;
            for (char c : word.toCharArray()) {
                if (temp.nextLevel[c - 'a'] == null) {
                    temp.nextLevel[c - 'a'] = new Node(c);
                }
                temp = temp.nextLevel[c - 'a'];
            }
            temp.isLetter = true;
        }
        
        public boolean contains(String word) {
            Node temp = root;
            for (char c : word.toCharArray()) {
                if (null == temp.nextLevel[c - 'a']) {
                    return false;
                } else {
                    temp = temp.nextLevel[c - 'a'];
                }
            }
            return temp.isLetter;
        }
        
    }
    
    
    public List<String> findWords(char[][] board, String[] words) {
        Trie dict = new Trie();
        
        for (String word : words) {
            dict.add(word);
        }

        List<String> result = new ArrayList<>();
        boolean[][] visited = new boolean[board.length][board[0].length];
        
        for (int i = 0; i < board.length; i ++) {
            for (int j = 0; j < board[0].length; j ++) {
                contains(dict.root, i, j, visited, board, new StringBuilder(), result);
            }
        }
        
        return result;

    }
    
    public void contains(Node temp, int i, int j, boolean[][] visited, char[][] board, StringBuilder sb, List<String> res) {
        if (temp.isLetter && !res.contains(sb.toString())) {
            res.add(sb.toString());
        }
        if (i < 0 || i >= visited.length || j < 0 || j >= visited[0].length || visited[i][j]) return;
        char tempC = board[i][j];
        if (temp.nextLevel[tempC - 'a'] == null) return;
        temp = temp.nextLevel[tempC - 'a'];
        visited[i][j] = true;
        sb.append(board[i][j]);
        int length = sb.length();
        
        
        for (int m = 0; m < 4; m ++) {
            int horizontal = MOVE[m];
            int vertical = MOVE[m + 1];
            contains(temp, i + horizontal, j + vertical, visited, board, sb, res);
            sb.setLength(length);
        }
        visited[i][j] = false;  
    }
}