DFS flood filling

Word Search, 这里除了用一个visited数组去记录之前走过的path，还是把值设成特殊字符，进而剩下了空间

public class Solution {

    int[] dx = {0, 0, -1, 1};
    int[] dy = {1, -1, 0, 0};

    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (dfs(board, i, j, word, 0)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

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

        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];

            char c = board[i][j];
            board[i][j] = '#';
            if (dfs(board, x, y, word, index + 1)) {
                return true;
            }
            board[i][j] = c;
        }

        return false;
    }
}

Surrounded Regions, 这题用dfs写的时候，如果允许访问边上的点，会导致stack over flow, 在dfs之前判断一下，不去访问边上的点。

public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
            return;
        }

        int m = board.length, n = board[0].length;

        for (int i = 0; i < m; i++) {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'M') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private void dfs(char[][] board, int i, int j) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') {
            return;
        }

        board[i][j] = 'M';

        if (i - 1 > 0) {
            dfs(board, i - 1, j);
        }
        if (i + 1 < board.length - 1) {
            dfs(board, i + 1, j);
        }
        if (j - 1 > 0) {
            dfs(board, i, j - 1);
        }
        if (j + 1 < board[0].length - 1) {
            dfs(board, i, j + 1);
        }
    }
}

Number of Islands, 如果input是允许修改的话，后面写的解法是可以的。如果input不允许修改，那就加一个visited数组确保不访问同一个点多次。

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return 0;
        }

        int m = grid.length, n = grid[0].length;

        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }

        return count;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }

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

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