【leetcode】Palindrome Partitioning II

Question ：

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.

For example, given s = `"aab"`, Return `1` since the palindrome partitioning `["aa","b"]` could be produced using 1 cut.

Anwser 1 ：

```class Solution {
public:
int minCut(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (s.size() < 2)
return 0;
int length = s.size();
int *minSegs = new int[length+1];
minSegs[0] = 0;
minSegs[1] = 1;
int **dp = new int*[2];
dp[0] = new int[length+2];
dp[1] = new int[length+2];
dp[0][0] = dp[1][0] = 0;
dp[0][1] = dp[1][1] = 1;
dp[0][2] = -1;

int cur = 0;
int pre = 1;
for (int i=1; i<s.size(); i++) {
int cur = i % 2;
int pre = (i +1) % 2;
minSegs[i+1] = minSegs[i] + 1;
int n = 1;
for (int j=0; dp[pre][j] != -1; j++) {
int left = i-1-dp[pre][j];
if (left>=0 && s[left]==s[i]) {
dp[cur][++n] = dp[pre][j] + 2;
if (minSegs[left] + 1 < minSegs[i+1])
minSegs[i+1] = minSegs[left] + 1;
}
}
dp[cur][++n] = -1;
}

int min = minSegs[s.size()] - 1;
delete []minSegs;
return min;
}
};```

Anwser 2: ：

```class Solution {
public:
int minCut(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int len=s.length();
int BIG=2*len;
int num_line=len+1;
vector<int> isPalindrome(num_line*num_line);
for(int l=1;l<=len;l++)//两个木板之间有多少个字符
{
for (int i=0;i+l<num_line;i++)//从第0个木板开始,i+l为木板的序号
{
if (l==1)
{
isPalindrome[i*num_line+(i+l)]=1;
}
else if(l==2)
{
if (s[i]==s[i+l-1])
isPalindrome[i*num_line+(i+l)]=1;
else
isPalindrome[i*num_line+(i+l)]=BIG;
}
else
{
if (s[i]==s[i+l-1])
isPalindrome[i*num_line+(i+l)]=isPalindrome[(i+1)*num_line+(i+l-1)];
else
isPalindrome[i*num_line+(i+l)]=BIG;
}
}
}
vector<int> dist(num_line);
vector<bool> labeled(num_line);
for(int i=0;i<num_line;i++)
{
dist[i]=BIG;
labeled[i]=false;
}
dist[0]=0;
labeled[0]=true;
int current_line=0;
for(int i=1;i<num_line;i++)
{
for(int d=current_line+1;d<num_line;d++)//对所有的相邻（在图中）的木板
{
if(!labeled[d])
{
if (dist[current_line]+isPalindrome[current_line*num_line+d]<dist[d])
{
dist[d]=dist[current_line]+isPalindrome[current_line*num_line+d];
}
}
}
int mindist=BIG;
int minindex=-1;
for(int i=0;i<num_line;i++)
{
if(!labeled[i])
{
if(mindist>dist[i])
{
minindex=i;
mindist=dist[i];
}
}
}
current_line=minindex;
labeled[minindex]=true;
}

return dist[num_line-1]-1;
}
};```

0 条评论

• 【leetcode】Two Sum

Given an array of integers, find two numbers such that they add up to a specific...

• 【leetcode】Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you ma...

• 【leetcode】Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive ...

• POJ 刷题系列：1083. Moving Tables

POJ 刷题系列：1083. Moving Tables 传送门：POJ 1083. Moving Tables 题意： 一条走廊，两栏房间。搬运工每次从房价...

• HYSBZ 3676 回文串 (回文树)

3676: [Apio2014]回文串 Time Limit: 20 Sec  Memory Limit: 128 MB Submit: 1680  Solve...

• 【每日算法Day 70】图解算法：小学生都会的数块数问题，你会吗？

在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。

• HDU4352 XHXJ's LIS(LIS 状压)

刚开始的思路是\$f[i][j]\$表示到第\$i\$位，LIS长度为\$j\$的方案。 然而发现根本不能转移，除非知道了之前的状态然后重新dp一遍。。

• BZOJ4299: Codechef FRBSUM(主席树)

那么若\$a[i + 1] > s_i + 1\$，那么\$a[i + 1]\$不能被拼成