做网站的几个软件,高端建盏的价格,客户管理系统的设计与实现,做网站如何让盈利来源#xff1a;LeetCode第1278题
难度#xff1a;苦难
描述#xff1a;给你一个由小写字母组成的字符串s#xff0c;和一个整数k#xff0c;请按照下面的要求分割字符串:首先#xff0c;你可以将s中的部分字符修改为其他的小写字母。接着你需要把s分割成k个非空不想交…来源LeetCode第1278题
难度苦难
描述给你一个由小写字母组成的字符串s和一个整数k请按照下面的要求分割字符串:首先你可以将s中的部分字符修改为其他的小写字母。接着你需要把s分割成k个非空不想交的子串并且每个子串都是回文串请返回以这种方式分割字符串所需要修改的最少字符数。
示例1
输入:sabc,k2 输出1 解释可以把字符串分割成ab和c,并修改ab中的一个字符将它变为回文串。
分析在遇到字符串的问题可以联想到动态规划特别的是对于分割问题可以联想到动态规划最小可进行遍历从而可以定义一个动态二维数组dp[i][j]表示将字符串s的前i个字符串分割成k个回文子串所需要的最小字符串可以定义一个辅助函数int minChange(String s,int indexStart,int indexEnd)表示将s的第indexStart到indexEnd之间的字符串转化为回文串所需要的操作次数从而可以计算for(int ki-1;k0;k--){dp[i][j]Math.min(dp[i][j],dp[k][j-1]minChange(k1,i1))}即可
private int minChange(String s,int indexStart,int indexEnd)
{
int count0;
int beginIndexindexStart;
int endIndexindexEnd;
while(endIndexbeginIndex)
{
if(s.charAt(beginIndex)!s.charAt(indexEnd))
{
endIndex--;
beginIndex;
}else
{
count;
endIndex--;
beginIndex;
}
}
return count;
}
public int getMinChange(String s,int k)
{
int dp[][]new int[s.length()][k1];
for(int i0;is.length();i)
{
dp[i][0]0;
}
for(int i1;is.length();i)
{
for(int j1;jk1;j)
{
dp[i][j]Interger.MAX_VALUE;
for(int mi-1;m0;m--)
{
dp[i][j]Math.min(dp[i][j],dp[m][j-1]minChange(m1,i1));
}
}
}
return dp[s.length()-1][k];
}
