1
class Solution {
2
 public:
3
  vector<vector<int>> dp1;
4
  bool isPalindrome(string &s, int i, int j) {
5
    if (i >= j) return true;
6
    if (dp1[i][j] != -1) return dp1[i][j];
7
    if (s[i] == s[j]) return dp1[i][j] = isPalindrome(s, i + 1, j - 1);
8
    return dp1[i][j] = false;
9
  }
10
  bool checkPartitioning(string s) {
11
    int n = s.size();
12
    dp1.resize(n, vector<int>(n, -1));
13
    for (int i = 0; i < n; i++) {
14
      for (int j = i + 1; j < n - 1; j++) {
15
        if (isPalindrome(s, 0, i) && isPalindrome(s, i + 1, j) && isPalindrome(s, j + 1, n - 1))
16
          return true;
17
      }
18
    }
19
    return false;
20
  }
21
};