Maximal Square LeetCode solution in C++

1
class Solution {
2
 public:
3
  int dp[301][301];
4
  int helperMethod(int i, int j, vector<vector<char>> &matrix) {
5
    if (i < 0 || j < 0 || i >= matrix.size() || j >= matrix[0].size() || matrix[i][j] == '0')
6
      return 0;
7
    if (dp[i][j] != -1) return dp[i][j];
8

9
    return dp[i][j] =
10
               1 + min(helperMethod(i + 1, j, matrix),
11
                       min(helperMethod(i + 1, j + 1, matrix), helperMethod(i, j + 1, matrix)));
12
  }
13
  int maximalSquare(vector<vector<char>> &matrix) {
14
    int m = matrix.size();
15
    int n = matrix[0].size();
16
    int ans = INT_MIN;
17
    memset(dp, -1, sizeof(dp));
18
    for (int i = 0; i < m; i++) {
19
      for (int j = 0; j < n; j++) {
20
        if (matrix[i][j] == '1') {
21
          ans = max(ans, helperMethod(i, j, matrix));
22
        }
23
      }
24
    }
25
    return ans == INT_MIN ? 0 : ans * ans;
26
  }
27
};