73. Set Matrix Zeroes - Medium

前往題目

想法

• 遇到0就直接整行和整列換成0，這樣時間是O(m * n (m + n))
• 感覺比較適合用DFS

思路

結果不是BFS也不是DFS，因為不是感染的方式，而是只看初始狀態

1. 第一行和第一列拿來當作儲存空間，遇到cell為0的就直接把最上面和最左邊的cell賦值為0，這還算是紀錄而已(因為只紀錄在第一行和第一列)
2. 實際把該為0的cell替換為0(但是不替換第一行和第一列，要保持原始狀態)
3. 最後再把第一行或第一列該為0的話就換成0

Code

Neetcode大大講得非常清楚，從brute force一步步慢慢優化

class Solution {
    public void setZeroes(int[][] matrix) {
        final int ROWS = matrix.length, COLS = matrix[0].length;
        boolean rowZero = false; // Overlapping cell, for first row

        // Check and record which rows and cols should be zero
        for (int row = 0; row < ROWS; ++row) {
            for (int col = 0; col < COLS; ++col) {
                if (matrix[row][col] == 0) {
                    matrix[0][col] = 0;
                    // Handle overlapping cell
                    if (row > 0) {
                        matrix[row][0] = 0;
                    } else {
                        rowZero = true;
                    }
                }
            }
        }

        // Assign zeros
        for (int row = 1; row < ROWS; ++row) {
            for (int col = 1; col < COLS; ++col) {
                if (matrix[row][0] == 0 || matrix[0][col] == 0) {
                    matrix[row][col] = 0;
                }
            }
        }
        
        // Assign zeros to the first row and col
        if (matrix[0][0] == 0) {
            for (int row = 0; row < ROWS; ++row) {
                matrix[row][0] = 0;
            }
        }

        if (rowZero) {
            for (int col = 0; col < COLS; ++col) {
                matrix[0][col] = 0;
            }
        }
    }
}