LeetCode - Palindrome Partitioning II

 1 // 1WA, 1AC, O(n^2) solution with DP
 2 #include <string>
 3 using namespace std;
 4 
 5 class Solution {
 6 public:
 7     int minCut(string s) {
 8         int **pal = nullptr;
 9         int *dp = nullptr;
10         int len = (int)s.size();
11         
12         if (len <= 1) {
13             return 0;
14         }
15         
16         pal = new int*[len];
17         dp = new int[len + 1];
18         
19         int i, j;
20         for (i = 0; i < len; ++i) {
21             pal[i] = new int[len];
22         }
23         for (i = 0; i < len; ++i) {
24             for (j = 0; j < len; ++j) {
25                 pal[i][j] = 0;
26             }
27         }
28         
29         // pal[i][j] means whether the substring s[i:j] is a palindrome.
30         for (i = 0; i < len; ++i) {
31             pal[i][i] = 1;
32         }
33         for (i = 0; i < len - 1; ++i) {
34             pal[i][i + 1] = (s[i] == s[i + 1]) ? 1 : 0;
35         }
36         for (i = 2; i <= len - 1; ++i) {
37             for (j = 0; j + i < len; ++j) {
38                 pal[j][j + i] = (pal[j + 1][j + i - 1] && (s[j] == s[j + i])) ? 1 : 0;
39             }
40         }
41         
42         // dp[i] means the minimal number of segments the substring s[0:i] 
43         // must be cut, so that they‘re all palindromes.
44         dp[0] = 0;
45         for (i = 1; i <= len; ++i) {
46             dp[i] = i;
47             for (j = 0; j < i; ++j) {
48                 if (pal[j][i - 1]) {
49                     dp[i] = mymin(dp[j] + 1, dp[i]);
50                 }
51             }
52         }
53         
54         int ans = dp[len];
55         for (i = 0; i < len; ++i) {
56             delete[] pal[i];
57         }
58         delete[] pal;
59         delete[] dp;
60         
61         return ans - 1;
62     }
63 private:
64     int mymin(const int x, const int y) {
65         return (x < y ? x : y);
66     }
67 };