This is one of those problems where the clean idea matters more than the amount of code. For 1278. Palindrome Partitioning III, the solution in this repository is mainly a DFS + memoization solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: DFS + memoization, dynamic programming.
The notes already sitting in the source point us in the right direction:
- recursion(dfs)
- https://leetcode.com/problems/palindrome-partitioning-iii/discuss/441427/Python3-Top-down-DFS-with-Memoization
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are cost, dfs, palindromePartition.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//recursion(dfs)
02//Runtime: 16 ms, faster than 72.66% of C++ online submissions for Palindrome Partitioning III.
03//Memory Usage: 6.6 MB, less than 100.00% of C++ online submissions for Palindrome Partitioning III.
04//https://leetcode.com/problems/palindrome-partitioning-iii/discuss/441427/Python3-Top-down-DFS-with-Memoization
05class Solution {
06public:
07 vector<vector<int>> memo;
08 int n;
09
10 int cost(string& s, int start, int end){
11 int res = 0;
12 /*
13 exit when the remaining part has 0 or 1 char,
14 that is, start == end(only 1 char) or
15 start > end(only 0 char)
16 */
17 for(; start < end; start++, end--){
18 if(s[start] != s[end]) res++;
19 }
20 return res;
21 }
22
23 int dfs(string& s, int start, int k){
24 if(memo[start][k] != INT_MAX){
25 return memo[start][k];
26 }
27
28 /*
29 the problem doesn't allow k > s.size(),
30 so we can just use == here,
31 if the limit doesn't exist,
32 we need <= here
33 */
34 // if(n - start <= k){
35 if(n - start == k){
36 /*
37 the current string to be partitioned is
38 s[start, n-1], and its length is n-start,
39 if the length is (less than or) equal to k,
40 we can partition it to k parts and
41 each part having length 1,
42 so the cost will be 0
43 */
44 return 0;
45 }
46
47 if(k == 1){
48 //can't be partitioned anymore
49 return cost(s, start, n-1);
50 }
51
52 /*
53 next <= n-k+1:
54 looing at dfs(s, next, k-1),
55 next will be n-k+1 and k will be k-1,
56 so in next recursion,
57 n - start == k will holds and return 0,
58 this is the base where we can split the remaing string into k parts
59 */
60 // for(int next = start+1; next <= n-k+1; next++){
61 // for(int next = start+1; next <= n-1; next++){ //must be used with if(n - start <= k){
62 memo[start][k] = min(memo[start][k], cost(s, start, next-1)+dfs(s, next, k-1));
63 }
64
65 return memo[start][k];
66 }
67
68 int palindromePartition(string s, int k) {
69 n = s.size();
70 //padding for k's dimension, index 0 is meaningless
71 memo = vector<vector<int>>(n, vector(k+1, INT_MAX));
72
73 return dfs(s, 0, k);
74 }
75};
76
77//DP
78//https://leetcode.com/problems/palindrome-partitioning-iii/discuss/442083/Simple-C%2B%2B-Dp-O(N2K)-Beats-100-with-Explanation
79//Runtime: 20 ms, faster than 63.10% of C++ online submissions for Palindrome Partitioning III.
80//Memory Usage: 6.9 MB, less than 100.00% of C++ online submissions for Palindrome Partitioning III.
81class Solution {
82public:
83 int palindromePartition(string s, int K) {
84 int n = s.size();
85 //cost of s[i...j]
86 vector<vector<int>> cost(n, vector(n, 0));
87 //(#partitions, end index)
88 vector<vector<int>> dp(K+1, vector(n, n));
89
90 for(int i = n-1; i >= 0; i--){
91 for(int j = i; j < n; j++){
92 //cost of s[i...j]
93 if(j == i){
94 cost[i][j] = 0;
95 }else if(j == i+1){
96 cost[i][j] = (s[i] != s[j]);
97 }else if(s[i] == s[j]){
98 cost[i][j] = cost[i+1][j-1];
99 }else{
100 cost[i][j] = cost[i+1][j-1]+1;
101 }
102 }
103 }
104
105 for(int k = 1; k <= K; k++){
106 for(int j = 0; j < n; j++){
107 if(k == 1){
108 //don't partition s[0...j]
109 dp[k][j] = cost[0][j];
110 }else{
111 for(int i = 0; i < j; i++){
112 //partition to [0...i] and [i+1...j]
113 dp[k][j] = min(dp[k][j], dp[k-1][i]+cost[i+1][j]);
114 }
115 }
116 }
117 }
118
119 return dp[K][n-1];
120 }
121};Cost