221. Maximal Square

QUESTION:

Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s 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

Constraints:

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

EXPLANATION:

这个题目就有点意思了. 思路我先写一下:

  1. 找出最大可能的框maxlengh, 也就是 max(m,n)
  2. 那既然框知道了, 那我们就可以将框从1-maxlength的框在matrix上移动
  3. 移动到一个位置后, 需要判断当前框内的所有位置是否是1
  4. 这样循环一遍后, 就能得到当前框是否可行.
  5. 再将框扩大1, 再从头开始移动, 直到最后框的结束

    SOLUTION:

    class Solution {
     func maximalSquare(_ matrix: [[Character]]) -> Int {
         var m:Int = matrix.count
         var n:Int = matrix[0].count
         var maxLength:Int = m > n ? n : m
         var result:Int = 0
         for length in 1...maxLength {
             for anchorX in 0...matrix[0].count-length {
                 for anchorY in 0...matrix.count-length {
                     var indexMaxX = anchorX + length <= matrix[0].count ? anchorX + length - 1 : matrix[0].count - 1
                     var indexMaxY = anchorY + length <= matrix.count ? anchorY + length - 1 : matrix.count - 1
                     var tmpResult:Bool = true
                     w: for indexX in anchorX...indexMaxX {
                         for indexY in anchorY...indexMaxY {
                             if matrix[indexY][indexX] == "0" {
                                 tmpResult = false
                                 break w
                             }
                         }
                     }
                     if tmpResult {
                         result = result < length ? length : result
                     }
                 }
             }
         }
         return result * result
     }
    }