Given a string s
, partition s
such that every substring of the partition is a palindrome.Return the minimum cuts needed for a palindrome partitioning of s
.
Example 1:
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Example 2:
Input: s = "a"
Output: 0
Example 3:
Input: s = "ab"
Output: 1
Constraints:
1 <= s.length <= 2000
-
s
consists of lower-case English letters only.
这种回文什么的,数据范围又小,一看就是 dp。但判断是否是回文数会很耗时间,因此我们先做一下预处理。
对于位置 i
,它自身是一个回文串。然后我们向两边扩展,如果 s[i-j]==s[i+j]
,那么从 i-j
到 i+j
就是个回文串。一旦出现 s[i-j]!=s[i+j]
,那么剩下的就一定都不是回文串了。
上面是回文串元素个数为奇数的情况,偶数的同理,判断 s[i-j]==s[i+j+1]
即可。这样我们就得到了任意字符串是否为回文串,时间复杂度
O
(
n
2
)
O(n^2)
O(n2)
然后就是 dp,定义 f[i]
为从 0 到 i 的子串最少要分割多少次,状态转移方程为 f[i]=min(f[i],f[j-1]+1)
,其中,j 到 i 的子串为回文串。初始条件为 f[0]=0
。时间复杂度
O
(
n
2
)
O(n^2)
O(n2)
下面是代码
class Solution {
public:
int minCut(string s) {
bool isPartition[2001][2001];//判断是否为回文串
int f[2001];
int len = s.length();
for (int i = 0; i < len; i++) {//回文串元素数目为奇数
isPartition[i][i] = true;
int j = 1;
while (i - j >= 0 && i + j < len && s[i - j] == s[i + j]) {
isPartition[i - j][i + j] = true;
j++;
}
while (i - j >= 0 && i + j < len) {
isPartition[i - j][i + j] = false;
j++;
}
}
for (int i = 0; i < len - 1; i++) {//回文串元素数目为偶数
int j = 0;
while (i - j >= 0 && i + j + 1 < len && s[i - j] == s[i + j + 1]) {
isPartition[i - j][i + j + 1] = true;
j++;
}
while (i - j >= 0 && i + j + 1 < len) {
isPartition[i - j][i + j + 1] = false;
j++;
}
}
f[0]=0;
for (int i = 1; i < len; i++) {//dp
f[i] = 9999;//取一个较大的数
if (isPartition[0][i])
f[i] = 0;
else
for (int j = 1; j <= i; j++)
if (isPartition[j][i])
f[i] = min(f[i], f[j - 1] + 1);
}
return f[len - 1];
}
};
Status | Runtime | Memory |
---|---|---|
Accepted | 16 ms | 10.3 MB |
实际上做一做剪枝还可以更快,比如判断回文的同时就进行 dp,把最小分割次数给算出来。状态转移方程 f[i+j+1] = min(f[i+j+1],1+f[i-j])
和 f[i+j+1] = min(f[i+j+1],1+f[i-j+1])
class Solution {
public:
int minCut(string s) {
int len = s.length();
int f[len + 1];
for (int i = 0; i <= len; i++)
f[i] = i-1;
for (int i = 0; i < len; i++) {
for (int j = 0; i-j >= 0 && i+j < len && s[i-j]==s[i+j] ; j++)
f[i+j+1] = min(f[i+j+1],1+f[i-j]);
for (int j = 1; i-j+1 >= 0 && i+j < len && s[i-j+1] == s[i+j]; j++)
f[i+j+1] = min(f[i+j+1],1+f[i-j+1]);
}
return f[len];
}
};
Status | Runtime | Memory |
---|---|---|
Accepted | 4 ms | 6.1 MB |
这下子终于全部进了前 1%
Runtime: 4 ms, faster than 99.85% of C++ online submissions for Palindrome Partitioning II.
Memory Usage: 6.1 MB, less than 99.88% of C++ online submissions for Palindrome Partitioning II.