|
| 1 | +// Time: O(n) |
| 2 | +// Space: O(n) |
| 3 | + |
| 4 | +classSolution { |
| 5 | +public: |
| 6 | +boolcheckPartitioning(string s) { |
| 7 | +returnmodifiedManacher(s); |
| 8 | + } |
| 9 | + |
| 10 | +private: |
| 11 | +boolmodifiedManacher(const string& s) { |
| 12 | + string T =preProcess(s); |
| 13 | +constint n = T.length(); |
| 14 | + vector<int>P(n); |
| 15 | + vector<bool>dp1(n);// dp1[i]: s[:i] is a palindromic string |
| 16 | + vector<bool>dp2(n);// dp2[i]: s[:i+1] is composed of 2 palindromic strings |
| 17 | +int C =0, R =0; |
| 18 | +for (int i =1; i < n -1; ++i) { |
| 19 | +int i_mirror =2 * C - i; |
| 20 | + P[i] = (R > i) ?min(R - i, P[i_mirror]) :0; |
| 21 | +while (T[i +1 + P[i]] == T[i -1 - P[i]]) { |
| 22 | +if (dp1[i -1 - P[i]]) { |
| 23 | + dp2[i +1 + P[i]] =true; |
| 24 | + } |
| 25 | + ++P[i]; |
| 26 | + } |
| 27 | +if (i +1 + P[i] == n -1 && dp2[i -1 - P[i]]) { |
| 28 | +returntrue; |
| 29 | + } |
| 30 | +if (i -1 - P[i] ==0) { |
| 31 | + dp1[i +1 + P[i]] =true; |
| 32 | + } |
| 33 | +if (i + P[i] > R) { |
| 34 | + C = i; |
| 35 | + R = i + P[i]; |
| 36 | + } |
| 37 | + } |
| 38 | +returnfalse; |
| 39 | + } |
| 40 | + |
| 41 | + stringpreProcess(const string& s) { |
| 42 | +if (s.empty()) { |
| 43 | +return"^$"; |
| 44 | + } |
| 45 | + string ret ="^"; |
| 46 | +for (int i =0; i < s.length(); ++i) { |
| 47 | + ret +="#" + s.substr(i,1); |
| 48 | + } |
| 49 | + ret +="#$"; |
| 50 | +return ret; |
| 51 | + } |
| 52 | +}; |
| 53 | + |
| 54 | +// Time: O(n^2) |
| 55 | +// Space: O(n) |
| 56 | +classSolution2 { |
| 57 | +public: |
| 58 | +boolcheckPartitioning(string s) { |
| 59 | + vector<vector<bool>>dp(size(s), vector<bool>(size(s))); |
| 60 | +for (int i =size(s) -1; i >=0; --i) { |
| 61 | +for (int j = i; j <size(s); ++j) { |
| 62 | +if (s[i] == s[j] && (j - i <2 || dp[i +1][j -1])) { |
| 63 | + dp[i][j] =true; |
| 64 | + } |
| 65 | + } |
| 66 | + } |
| 67 | +for (int i =1; i +1 <size(s); ++i) { |
| 68 | +for (int j = i +1; j <size(s); ++j) { |
| 69 | +if (dp[0][i -1] && dp[i][j -1] && dp[j][size(s) -1]) { |
| 70 | +returntrue; |
| 71 | + } |
| 72 | + } |
| 73 | + } |
| 74 | +returnfalse; |
| 75 | + } |
| 76 | +}; |