Word Search

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. [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "SEE", -> returns true, word = "ABCB", -> returns false.

• 是否访问过的backtracking
• 注意溢出条件的判断

public boolean exist(char[][] board, String word) {
    for(int i = 0; i < board.length; i++)
        for(int j = 0; j < board[0].length; j++){
            if(exist(board, i, j, word, 0))
                return true;
        }
    return false;
}
private boolean exist(char[][] board, int i, int j, String word, int ind){
    if(ind == word.length()) return true;
    if(i > board.length-1 || i <0 || j<0 || j >board[0].length-1 || board[i][j]!=word.charAt(ind))
        return false;
    board[i][j]='*'; // no extra space use
    boolean result =    exist(board, i-1, j, word, ind+1) ||
                        exist(board, i, j-1, word, ind+1) ||
                        exist(board, i, j+1, word, ind+1) ||
                        exist(board, i+1, j, word, ind+1);
    board[i][j] = word.charAt(ind);
    return result;
}

Word Search II

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

• 需要求出所有的结果，所以需要运用dfs
• 为了提升效率，需要用到trie，这样可以提前将不符合的prefix跳出搜索
• 因为是求所有的结果，最后加入的结果，可能存在重复（对每个点都进行了dfs），所以res先用一个hashset

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

        int row = board.length;
        int col = board[0].length;

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

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                helper(board, i, j, "", trie, res);
            }
        }         
        return new ArrayList<>(res);
    }

    private void helper(char[][] board, int x, int y, String str, Trie trie, Set<String> res) {
        if (!isValid(board, x, y)) return;
        if (board[x][y] == '*') return;

        char c = board[x][y];
        str += c;
        if (!trie.startsWith(str)) 
            return;

        if (trie.search(str)) 
            res.add(str);        

        board[x][y] = '*';
        helper(board, x+1, y, str, trie, res);
        helper(board, x-1, y, str, trie, res);
        helper(board, x, y+1, str, trie, res);
        helper(board, x, y-1, str, trie, res);
        board[x][y] = c;           
    }