79. Word Search

这类在 2D 矩阵上 DFS 的题都挺送分的，写的时候重在简洁。 和这题非常相似的还有下面的 Number of Islands. 边界处理在 DFS 一开始做，免得后面的多向 DFS 里再重写

如果要 backtrack，就先把自己格子设成其他字符再 DFS，免得死循环

这个的作用其实就跟permutation II里面那个visited数组的作用差不多，相当于你是visited[i][j] = 1

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) return false;

        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                if (dfs(board, word, 0, i, j)) return true;
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, String word, int index, int row, int col) {
        if (index == word.length()) return true;
        if (row < 0 || row >= board.length) return false;
        if (col < 0 || col >= board[0].length) return false;
        if (board[row][col] != word.charAt(index)) return false; 

        board[row][col] = '#';

        boolean rst = (dfs(board, word, index + 1, row - 1, col) ||
                       dfs(board, word, index + 1, row + 1, col) ||
                       dfs(board, word, index + 1, row, col + 1) ||
                       dfs(board, word, index + 1, row, col - 1));

        board[row][col] = word.charAt(index);

        return rst;
    }
}

212. Word Search II

public class Solution {
    private class TrieNode {
        char ch;
        TrieNode[] map;
        boolean isWord;

        public TrieNode() {
            map = new TrieNode[26];
        }
        public TrieNode(char ch) {
            this.ch = ch;
            map = new TrieNode[26];
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        if (board == null || board.length == 0 || 
            words == null || words.length == 0) return result;

        TrieNode root = new TrieNode();
        for (String word : words) {
            add(word, root);
        }

        for (int i = 0; i < board.length; ++i) {
            for (int j = 0; j < board[0].length; ++j) {
                searchAdd(root, board, i, j, result, new StringBuilder());
            }
        }
        return result;
    }

    private void add(String word, TrieNode root) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.map[index] == null) {
                node.map[index] = new TrieNode(ch);
            }
            node = node.map[index];
        }
        node.isWord = true;
    }

    private void searchAdd(TrieNode root, char[][] board, int row, int col, 
                          List<String> result, StringBuilder sb) {
        if (root.isWord) {
            if (!result.contains(sb.toString())) result.add(sb.toString());
        }

        if (row < 0 || row >= board.length) return;
        if (col < 0 || col >= board[0].length) return;

        if (board[row][col] == '#') return;

        char ch = board[row][col];
        int index = ch - 'a';
        if (root.map[index] == null) {
            return;
        } else {
            int len = sb.length();
            sb.append(ch);
            board[row][col] = '#';

            searchAdd(root.map[index], board, row + 1, col, result, sb);
            searchAdd(root.map[index], board, row - 1, col, result, sb);
            searchAdd(root.map[index], board, row, col + 1, result, sb);
            searchAdd(root.map[index], board, row, col - 1, result, sb);

            board[row][col] = ch;
            sb.setLength(len);
        }
    }
}

200. Number of Islands

和上一道 Word Search 就完全是一个套路，只是细节不同，这题 DFS 的主要动作是 flood-filling，把相连接的所有格子都填上，算作一个岛。既然不是 search 就不需要 backtracking 那一套了，填就行。

基本步骤就是我们每次遇到1，也就是遇到一个岛的时候，就DFS，然后再DFS的时候再去看它上下左右还有没有连接的岛，有的话继续DFS，把它们都算作一个岛，count加一次，并且都填成0，就是填成海，这样以后就遍历不到了。很简单的思路。

public class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[i].length; ++j) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length) return;
        if (j < 0 || j >= grid[0].length) return;

        if (grid[i][j] == '0') return;

        grid[i][j] = '0';

        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
        dfs(grid, i - 1, j);
    }
}