LeetCode：221. Largest Square

In a ‘0’ and ‘1’ In the two-dimensional matrix , Found contains only ‘1’ The largest square of , And return its area .

Example 1：

 Input ：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
 Output ：4

Example 2：

 Input ：matrix = [["0","1"],["1","0"]]
 Output ：1

Example 3：

 Input ：matrix = [["0"]]
 Output ：0

Tips ：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] by ‘0’ or ‘1’

---

Their thinking

1. First define an array dp Said to [i][j] Is the maximum side length of the lower right corner of the square , Define a variable max_len Represents the side length of the largest square
2. State transition equation ：dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;（ The minimum value of the three is taken because it is necessary to form a square ）
3. Be careful ： If the points on the left and top are ’1’, be dp[i][j] = 1

Code

/** * @param {character[][]} matrix * @return {number} */
var maximalSquare = function(matrix) {
    
    let max_len = 0;
    let dp = Array.from(Array(matrix.length), () => Array(matrix[0].length).fill(0));
    for (let i = 0; i < matrix.length; i++) {
    
        for (let j = 0; j < matrix[i].length; j++) {
    
            if (matrix[i][j] === '1') {
    
                if (i === 0 || j === 0) {
    
                    dp[i][j] = 1;
                }else {
    
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
                }
                max_len = Math.max(max_len, dp[i][j]);
            }
        }
    }
    return max_len ** 2;
};