Leetcode 221 Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.
Solution 1: Use DP. dp[i][j] is the max length if matrix[i][j] is the bottom right corner of the square. (1) if matrix[i][j] is 0, dp[i][j]=0; (2) if matrix[i][j]=1, we need to check dp[i-1][j] and dp[i][j-1]; (2a) if they are different, it is smaller of the two plus 1. (2b) check if they are equal, say dp[i-1][j]=dp[i][j-1]=len, check if weather dp[i-len][j-len] is 0 or 1.

 public class Solution {  
   public int maximalSquare(char[][] matrix) {  
     int m=matrix.length;  
     if (m==0) return 0;  
     int n=matrix[0].length;  
     int[] dp=new int[n];  
     int res=0;  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) {  
         if (matrix[i][j]=='0') dp[j]=0;  
         else if (i==0 || j==0) dp[j]=1;  
         else if (dp[j]==dp[j-1]) {  
           int k=dp[j];  
           dp[j]=(matrix[i-k][j-k]=='0')?k:k+1;  
         }  
         else dp[j]=1+Math.min(dp[j-1],dp[j]);  
         res=Math.max(res,dp[j]);  
       }  
     }  
     return res*res;  
   }  
 }