221. Maximal Square - Medium

前往題目

想法

• 只想得到暴力解
• 覺得優化應該是從側邊開始，根據以往經驗，因為這樣才能memorize同時確保每次只有一種狀況，往內推進的時候也都能用到cache

思路

Top down

1. 從左上開始
2. 每個cell都檢查其右、下，斜右下，藉以更新當前cell
3. 直到最後就會得到一個紀錄每個格子最大square的表格

Time: O(M * N)
Space: O(M * N)

Bottom up(DP)

1. 從右下開始逐步蔓延，方法和top down一樣

Time: O(M * N)
Space: O(M * N)

這題的DP很好懂

Code

照著neetcode大大的code來寫卻是TLE，只好換成dp

以下解法TLE

// !!!!!!!!!!!!TLE!!!!!!!!!!!!!!!
class Solution {
    private int ROWS;
    private int COLS;
    // Map cell and its maxlength of square
    private Map<int[], Integer> map;

    public int maximalSquare(char[][] matrix) {
        ROWS = matrix.length;
        COLS = matrix[0].length;

        map = new HashMap();

        // Start finding
        helper(0, 0, matrix);

        int maxArea = 0;

        // Obtain the max area
        for (int area : map.values()) {
            maxArea = Math.max(maxArea, area);
        }

        return maxArea * maxArea;
    }

    // top down finding helper
    private int helper(int r, int c, char[][] matrix) {
        // Out of bound
        if (r >= ROWS || c >= COLS) return 0;

        int[] curCell = new int[]{r, c};

        if (!map.containsKey(curCell)) {
            int down = helper(r + 1, c, matrix);
            int right = helper(r, c + 1, matrix);
            int diag = helper(r + 1, c + 1, matrix);
            
            // Store current cell
            map.put(curCell, 0);

            // Could be a bigger square
            if (matrix[r][c] == '1') {
                map.put(
                    curCell, 
                    1 + Math.min(Math.min(down, right), diag)
                );
            }
        }
        return map.get(curCell);
    }
}

DP解法

class Solution {
    public int maximalSquare(char[][] matrix) {
        final int ROWS = matrix.length;
        final int COLS = matrix[0].length;

        int[][] dp = new int[ROWS + 1][COLS + 1];

        // Length of the square
        int maxLength = 0;

        // From bottom to the top
        for (int row = ROWS - 1; row >= 0; --row) {
            for (int col = COLS - 1; col >= 0; --col) {
                // Can be a bigger square
                if (matrix[row][col] == '1') {
                    // Update current cell's value
                    dp[row][col] = 1 + Math.min(
                        Math.min(dp[row][col + 1], dp[row + 1][col]), 
                        dp[row + 1][col + 1]);
                    // Update the length of the largest square
                    maxLength = Math.max(maxLength, dp[row][col]);
                }
            }
        }

        return maxLength * maxLength;
    }
}