79/130/200/733FloodFill/17/22/784字符串回溯

Flood Fill

提示：Flood 是「洪水」的意思，Flood Fill 直译是「泛洪填充」的意思，体现了洪水能够从一点开始，迅速填满当前位置附近的地势低的区域。类似的应用还有：PS 软件中的「点一下把这一片区域的颜色都替换掉」，扫雷游戏「点一下打开一大片没有雷的区域」。

下面这几个问题，思想不难，但是初学的时候代码很不容易写对，并且也很难调试。我们的建议是多写几遍，忘记了就再写一次，参考规范的编写实现（设置 visited 数组，设置方向数组，抽取私有方法），把代码写对。

79. 单词搜索

class Solution {
    private static final int[][] DIRECTIONS = {{-1,0}, {0, -1}, {0,1}, {1,0}};
    private int rows;
    private int cols;
    private int len;
    private boolean[][] visited;
    private char[] charArray;
    private char[][] board;
    public boolean exist(char[][] board, String word) {
        rows = board.length;
        if (rows==0){
            return false;
        }
        cols = board[0].length;
        visited = new boolean[rows][cols];

        this.len = word.length();
        this.charArray = word.toCharArray();
        this.board = board;

        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(dfs(i, j, 0)){
                    return true;
                }
            }
        }
        return false;

    }

    private boolean inArea(int x,int y){
        return x>=0 && x<rows && y>=0 && y<cols;
    }

    private boolean dfs(int x, int y, int begin){
        if(begin == len-1){
            return board[x][y] == charArray[begin];
        }
        if(board[x][y] == charArray[begin]){
            visited[x][y] = true;
            for(int[] direction:DIRECTIONS){
                int newX = x + direction[0];
                int newY = y + direction[1];
                if(inArea(newX,newY) && !visited[newX][newY]){
                    if(dfs(newX, newY, begin+1)){
                        return true;
                    }
                }
            }
            visited[x][y] = false;
        }
        return false;
    }
}

说明：

偏移量数组在二维平面内是经常使用的，可以把它的设置当做一个技巧，并且在这个问题中，偏移量数组内的 4 个偏移的顺序无关紧要；
说明：类似使用这个技巧的问题还有：「力扣」第 130 题：被围绕的区域、「力扣」第 200 题：岛屿数量。

对于这种搜索算法，我认为理解 DFS 和状态重置并不难，代码编写也相对固定，难在代码的编写和细节的处理，建议多次编写，自己多总结多思考，把自己遇到的坑记下。

130. 被围绕的区域

法一：深度优先遍历

关键：与边界相连 $O$ 不能被替换成 $X$

具体步骤：

• 第一步：把四周有 $O$ 的地方都替换成 $-$，在四周进行 floodfill 算法（染色）
• 第二步：再从头到尾遍历一遍，把$O$ 换成 $X$，把 $-$ 换成 $O$

class Solution {

    private static final int[][] DIRECTIONS = {{-1,0}, {0, -1}, {0, 1}, {1,0}};
    private int rows;
    private int cols;
    public void solve(char[][] board) {
        rows = board.length;
        if(rows==0) return;
        cols = board[0].length;
        if(cols==0) return;

        // 第一步：把四周的 0 以及与 0 连通的 0 都设置成 -
        // 第一列和最后一列
        for(int i=0; i<rows; i++){
            if(board[i][0] == 'O'){
                dfs(i, 0, board);
            }
            if(board[i][cols-1] == 'O'){
                dfs(i, cols-1, board);
            }
        }
        // 第一行和最后一行
        for(int i=0;i<cols;i++){
            if(board[0][i] == 'O'){
                dfs(0, i, board);
            }
            if(board[rows-1][i] == 'O'){
                dfs(rows-1, i, board);
            }
        }
        // 第二行：遍历一次棋盘
        // 1. 剩下的O就是被包围的O
        // 2. - 是原来不能被包围的O，恢复成O
        for(int i=0; i<rows;i++){
            for(int j=0;j<cols; j++){
                if(board[i][j] == 'O'){
                    board[i][j] = 'X';
                } else if(board[i][j] == '-'){
                    board[i][j] = 'O';
                }
            }
        }

    }

    private boolean inArea(int x, int y, int rows, int cols){
        return x>=0 && x<rows && y>=0 && y<cols;
    }

    private void dfs(int i, int j, char[][] board){
        if(inArea(i,j,rows,cols) && board[i][j]=='O'){
            board[i][j] = '-';
            for (int k=0; k<4; k++){
                int newX = i + DIRECTIONS[k][0];
                int newY = j + DIRECTIONS[k][1];
                dfs(newX, newY, board);
            }
        }
        
    }
}

• 时间复杂度：$O(rows * cols)$ ，其中 rows 和 cols 分别为矩阵的行数和列数， 深度优先遍历过程中，每一个单元格至多只会被标记一次
• 空间复杂度：$O(rows * cols)$ ，深度优先遍历最多使用的栈的开销为整个棋盘大小

法二：广度优先遍历

class Solution {

    private static final int[][] DIRECTIONS = {{-1,0}, {0, -1}, {0, 1}, {1,0}};
    private int rows;
    private int cols;
    public void solve(char[][] board) {
        rows = board.length;
        if(rows==0) return;
        cols = board[0].length;
        if(cols==0) return;

        // 第一步：把四周的‘O’ 全部推入队列，通过广度优先遍历，把’O‘连通的地方全部编辑
        Queue<int []> queue = new LinkedList<>();
        for(int i=0; i<rows; i++){
            if(board[i][0] == 'O'){
                queue.offer(new int[]{i, 0});
            }
            if(board[i][cols-1] == 'O'){
                queue.offer(new int[]{i, cols-1});
            }
        }
        for(int i=0; i<cols; i++){
            if(board[0][i] == 'O'){
                queue.offer(new int[]{0, i});
            }
            if(board[rows-1][i] == 'O'){
                queue.offer(new int[]{rows-1, i});
            }
        }
        while(!queue.isEmpty()){
            int[] top = queue.poll();
            int i = top[0];
            int j = top[1];
            board[i][j] = '-';
            for(int[] direction : DIRECTIONS){
                int newX = i + direction[0];
                int newY = j + direction[1];
                if(inArea(newX, newY, rows, cols) && board[newX][newY]=='O'){
                    queue.offer(new int[]{newX, newY});
                }
            }
        }
        // 第 2 步：恢复
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == '-') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
     private boolean inArea(int x, int y, int rows, int cols) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }

}

法三：并查集

• 把四周的 $O$ 都和一个虚拟节点合并起来
• 在内部，只看两个方向，把 $O$ 都合并起来
• 最后再扫一次数组，不和 虚拟节点 链接的 $O$都标记成 $X$

并查集的写法容易受到 floorfill的影响， 用并查集的时候，其实只用每一行的右边和下面都看一下，只针对 $O$， 能合并就合并一下。

class Solution {

    class UnionFind{
        private int[] parent;

        public UnionFind(int n){
            this.parent = new int[n];
            for(int i=0; i<n; i++){
                parent[i] = i;
            }
        }

        public boolean isConnected(int x, int y){
            return find(x) == find(y);
        }

        public int find(int x){
            while(x != parent[x]){
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        public void union(int x,int y){
            int xRoot = find(x);
            int yRoot = find(y);
            if(xRoot == yRoot){
                return;
            }
            parent[xRoot] = yRoot;
        }
    }

    private int getIndex(int x, int y, int cols){
        return x*cols +y;
    }

    public void solve(char[][] board) {
        int rows = board.length;
        if(rows == 0){
            return;
        }
        int cols = board[0].length;
        if(cols == 0){
            return;
        }

        UnionFind unionFind = new UnionFind(rows * cols + 1);
        int dummyNode = rows*cols;
        // 填写第一行和最后一行
        for(int j=0; j< cols; j++){
            if(board[0][j] == 'O'){
                unionFind.union(getIndex(0, j, cols), dummyNode);
            }
            if(board[rows-1][j] == 'O'){
                unionFind.union(getIndex(rows-1, j ,cols), dummyNode);
            }
        }
        // 填写第 1 列和最后一列
        for (int i = 1; i < rows - 1; i++) {
            if (board[i][0] == 'O') {
                unionFind.union(getIndex(i, 0, cols), dummyNode);
            }
            if (board[i][cols - 1] == 'O') {
                unionFind.union(getIndex(i, cols - 1, cols), dummyNode);
            }
        }

        int[][] directions = new int[][]{{0,1},{1,0}};
        for(int i=0;i<rows; i++){
            for(int j=0;j<cols;j++){
                if(board[i][j] == 'O'){
                    for(int[] direction : directions){
                        int newX = i + direction[0];
                        int newY = j + direction[1];
                        if(newX < rows && newY<cols && board[newX][newY] =='O'){
                            unionFind.union(getIndex(i, j, cols), getIndex(newX, newY, cols));
                        }
                    }
                }
            }
        }

        for (int i = 1; i < rows - 1; i++) {
            for (int j = 0; j < cols - 1; j++) {
                if (board[i][j] == 'O') {
                    if (!unionFind.isConnected(getIndex(i, j, cols), dummyNode)) {
                        board[i][j] = 'X';
                    }
                }
            }
        }


    }
}

200. 岛屿数量

Flood法：从一个区域中提取若干个连通的点与其他相邻区域分开。

从一个点扩散开，找到与其连通的点，其实就是从一个点卡死，进行一次深度优先或广度优先遍历，发现一片连着的区域。把与之相连的所有的格子都标记上，视为发现了一个「岛屿」。

深度优先：

class Solution {
    private boolean[][] visited;
    private int rows;
    private int cols;
    private static final int[][] DIRECTIONS = {{-1,0}, {0,-1}, {1,0}, {0,1}};
    private char[][] grid;
    public int numIslands(char[][] grid) {
        rows = grid.length;
        if(rows==0) return 0;
        cols = grid[0].length;
        if(cols==0) return 0;

        visited = new boolean[rows][cols];
        this.grid = grid;

        int count = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 如果是岛屿中的一个点，并且没有被访问过，就进行深度优先遍历
                if (!visited[i][j] && grid[i][j] == '1') {
                    dfs(i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private boolean inArea(int x, int y){
        return x>=0 && x<rows && y>=0 && y<cols;
    }

    private void dfs(int i, int j){
        visited[i][j] = true;
        for(int k=0;k<4;k++){
            int newX = i + DIRECTIONS[k][0];
            int newY = j + DIRECTIONS[k][1];
            // 如果不越界，还是陆地，没有被访问过
            if (inArea(newX, newY) && grid[newX][newY] == '1' && !visited[newX][newY]) {
                dfs(newX, newY);
            }

        }
    }
}

广度优先：

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    private final static int[][] DIRECTIONS = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
    private int rows;
    private int cols;
    private char[][] grid;
    private boolean[][] visited;

    public int numIslands(char[][] grid) {
        rows = grid.length;
        if (rows == 0) {
            return 0;
        }
        cols = grid[0].length;
        this.grid = grid;
        visited = new boolean[rows][cols];

        int count = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {
                    bfs(i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private void bfs(int i, int j) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(i * cols + j);
        // 注意：这里要标记上已经访问过
        visited[i][j] = true;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            int curX = cur / cols;
            int curY = cur % cols;
            for (int k = 0; k < 4; k++) {
                int newX = curX + DIRECTIONS[k][0];
                int newY = curY + DIRECTIONS[k][1];
                if (inArea(newX, newY) && grid[newX][newY] == '1' && !visited[newX][newY]) {
                    queue.offer(newX * cols + newY);
                    
                    visited[newX][newY] = true;
                }
            }
        }
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
}

并查集

关于连通性问题，并查集也是常用的数据结构

思路：并查集中维护连通分量的个数，在遍历的过程中：

• 相邻的陆地（只需要向右看和向下看）合并，只要发生过合并，岛屿数量就减一
• 在遍历过程中，同时记录空地的数量
• 并查集中连通分量的个数 - 空地的个数 = 岛屿数

733. 图像渲染

class Solution {

    int m,n;
    private int[][] directions = {{1,0},{0,1},{-1,0},{0,-1}};
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        m = image.length;
        n = image[0].length;

        int currColor = image[sr][sc];

        if(currColor!=newColor){
            dfs(sr, sc,currColor, newColor, image); 
        }

        return image;
    }

    private boolean inArea(int x, int y){
        return x>=0 && x<m && y>=0 && y<n;
    }

    private void dfs(int sr, int sc, int color, int newColor, int[][] image){
        if(image[sr][sc] == color){
            image[sr][sc] = newColor;
            for(int[] direct : directions){
                int newx = sr + direct[0];
                int newy = sc + direct[1];
                if(inArea(newx, newy)){
                    dfs(newx,newy, color, newColor, image);
                }
            }
        }
    }

}

17. 电话号码的字母组合

• 由于字符追加到后面，是新创建一个对象，因此 没有显式回溯（状态重置）的过程 ；

class Solution {

    public List<String> letterCombinations(String digits) {
        String[] digitsMap =  {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        List<String> res = new ArrayList<>();
        if(digits.length() == 0){
            return res;
        }

        findCombinations(digits, digitsMap, 0, "", res);
        return res;
    }

    private void findCombinations(String digits, String[] digitsMap, int start, String pre, List<String> res){
        if(start == digits.length()){
            res.add(pre);
            return;
        }

        String nextStr = digitsMap[digits.charAt(start) - '2'];
        int len = nextStr.length();
        for(int i=0; i<len; i++){
            findCombinations(digits, digitsMap, start+1, pre+nextStr.charAt(i), res);
        }
    }


}

784. 字母大小写全排列

大小写转换问题，使用异或运算转换。

ASCII表 A到Z，Z完了之后没有直接到a，中间间隔了6个字符

发现大写字符与其对应的小写字符的ASCII的差为32，32这个值是 $2^5$ 可以表示为 $ 1<<5$

变换大小写这件事等价于：

• 如果字符是小写字符，减去32得到大写字符
• 如果字符是大写字符，加上32得到小写字符

而这两者合并起来，就是给这个字符做一次不进位的加法，即异或上 $1<<5$​

class Solution {
    public List<String> letterCasePermutation(String s) {
        int n = s.length();
        List<String> res = new ArrayList<>();
        if(n==0){
            return res;
        }
        char[] charArray = s.toCharArray();
        dfs(charArray, 0, res);
        return res;
    }


    private void dfs(char[] charArray, int index, List<String> res){
        if(index == charArray.length){
            res.add(new String(charArray));
            return;
        }

        dfs(charArray, index+1, res);
        if(Character.isLetter(charArray[index])){
            charArray[index] ^= 1<<5;
            dfs(charArray, index+1, res);
        }
    }

}

22. 括号生成

方法一：深度优先遍历

我们以 n = 2 为例，画树形结构图。方法是 「做减法」。

画出图后可分析出的结论：

• 当前左右括号都有大于0个可以使用的时候，才可以产生分支。
• 产生左分支的时候，只看当前是否还有左括号可以使用
• 产生右分支的时候，还收到左分支的限制，右边剩余可以使用的括号数量一定得严格大于左边剩余的数量的时候，才可以阐释分支。
• 在左边和右边剩余的括号数都为0时结算

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if(n==0){
            return res;
        }

        dfs("",n , n, res);
        return res;
    }

    private void dfs(String curStr, int left, int right, List<String> res){
        // 因为每一次尝试，都是使用新的字符串变量所有无须回溯
        // 在递归终止的时候，直接把它天道结果集即可
        if(left==0 && right==0){
            res.add(curStr);
            return;
        }

        // 剪枝 （左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝，注意这个细节）
        if(left > right){
            return;
        }

        if(left>0){
            dfs(curStr + "(" , left-1, right, res);
        }
        
        if(right>0){
            dfs(curStr + ")", left , right-1, res);
        }

    }

}