文章目录一、最长回文子串解题思路代码实现及解析总结二、分割回文串 II解题思路代码实现及解析总结三、最长回文子序列解题思路代码实现及解析总结四、让字符串成为回文串的最少插入次数解题思路代码实现及解析总结一、最长回文子串Leetcode链接给你一个字符串 s找到 s 中最长的 回文子串。示例 1输入s “babad”输出“bab”解释“aba” 同样是符合题意的答案。解题思路该类题也是不能使用单个元素为定位的提供不了足够的信息所以我们以每个子串的首、尾进行定位状态表示dp[i][j]储存着以 i 位置为开始以 j 位置为末尾的子串是否为回文串的信息那么状态转移方程可以分三种情况讨论i 和 j 的位置有一下三种情况1i 和 j 重叠若s.charAt(i)s.charAt(j)则为回文串2i 和 j 相邻若s.charAt(i)s.charAt(j)则为回文串3i 和 j 中间有其他元素若s.charAt(i)s.charAt(j)且dp[i1][j-1]true则为回文串综上所述也就是两头的元素必须相同然后才有往下讨论的必要if(i1j)dp[i][j]直接为true否则等于dp[i1][j-1]dp[i][j]i1j?dp[i1][j-1]:true;。也不用对dp表进行初始化了第三种情况会越界的位置已经全在前两种情况中被处理过了但是要注意看状态转移方程的话dp表的填表顺序是i 从后往前j 从i的位置开始往后这样就可以将所有子串“是否为回文串”的信息全部保存在dp表里面了这是一个非常重要的信息该类型其他题目都以此为基础然后统计出最长的那个就行了代码实现及解析classSolution{publicStringlongestPalindrome(Strings){intns.length();boolean[][]dpnewboolean[n][n];intstart0,len0;//用来记录最长的回文子串//填表for(intin-1;i0;i--){//i从后往前for(intji;jn;j){//j从i的位置开始往后//得到i~j这段子串如果i、j位置的字符一样才继续往下判断if(s.charAt(i)s.charAt(j)){dp[i][j]i1j?dp[i1][j-1]:true;//一句话包含了所讨论的三种情况}//填完表后看看是否为回文串进行长度的筛选if(dp[i][j]j-i1len){//记录下较长的那个信息starti;lenj-i1;}}}returns.substring(start,startlen);}}总结复习解题思路二、分割回文串 IILeetcode链接给你一个字符串 s请你将 s 分割成一些子串使每个子串都是回文串。返回符合要求的 最少分割次数 。示例 1输入s “aab”输出1解释只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。示例 2输入s “a”输出0解题思路状态表示还是使用常用的经验dp[i]表示从0~i 这段范围内的字符串的最少分割次数依题意我们知道我们要将该字符串进行分割那么如果①0~i 这段字符串就是一个回文串的话它就不需要再分割了dp[i]0如果②它不是一个回文串的话那么我们可以先在1 ~ i 这段范围内找到一个分割点 j使得分割后的[j ~i]最后这个子串为回文串j 不能等于0是因为j 0就是①这种情况这样以来便可结合状态表示去推导出状态转移方程dp[i]Math.min(dp[j-1]1,dp[i]);因为可能会找出多个分割点所以我们取最小值既然要取最小值dp[i]的初始值就应该初始化为正无穷避免干扰取值可以看到我们的解题逻辑中多次对一个字符串是否为回文串进行了判断那使用上题中所介绍的方法将所有子串“是否为回文串”的信息全部先保存在另一个dp表里面即可代码实现及解析classSolution{publicintminCut(Strings){//先将所有的子串“是否为回文串”的信息存起来intns.length();boolean[][]isPalnewboolean[n][n];for(intin-1;i0;i--){for(intji;jn;j){if(s.charAt(i)s.charAt(j)){isPal[i][j]i1j?isPal[i1][j-1]:true;}}}//然后是本题的主逻辑int[]dpnewint[n];for(inti0;in;i)dp[i]Integer.MAX_VALUE;//dp表的初始化//填表for(inti0;in;i){if(isPal[0][i])dp[i]0;//如果该段子串就是个回文串那么就不需要再分割了else{for(intj1;ji;j){//在0~i这段范围内找到一个分割点j使得分割后的[j~i]最后这段子串为回文串if(isPal[j][i]){dp[i]Math.min(dp[j-1]1,dp[i]);//状态转移方程}}}}returndp[n-1];}}总结复习解题思路三、最长回文子序列Leetcode链接给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。解题思路从第一题的子串变成了子序列方法一用第一题的方法进行修改状态表示dp[i][j]表示以 i 位置为首以 j 位置为末尾的子序列中最长的回文子序列的长度这样当我们计算dp[i][j]时确定i、j 位置要遍历字符串在i~j 范围内寻找可以匹配的序列的边界时又要遍历来固定 left 和 right 会造成较大的时间复杂度。所以应该使用方法二方法二状态表示dp[i][j]表示在 i~j 这段范围内最长的回文子序列的长度字符串仍分三种情况讨论当s.charAt(i)s.charAt(j)时①dp[i][j]1;②dp[i][j]2;③dp[i][j]dp[i1][j-1]2;当s.charAt(i)!s.charAt(j)时dp[i][j]Math.max(dp[i][j-1],dp[i1][j]);分别去掉两边的一个元素再找最长回文子序列就行了遇到回文串类子序列问题还是要采用方法二的这种范围化状态表示代码实现及解析classSolution{publicintlongestPalindromeSubseq(Strings){intns.length();int[][]dpnewint[n][n];//填表for(intin-1;i0;i--){dp[i][i]1;//可以先处理一下i、j重合的情况for(intji1;jn;j){if(s.charAt(i)s.charAt(j)){dp[i][j]i1j?dp[i1][j-1]2:2;}else{dp[i][j]Math.max(dp[i][j-1],dp[i1][j]);}}}returndp[0][n-1];}}总结复习解题思路四、让字符串成为回文串的最少插入次数Leetcode链接给你一个字符串 s 每一次操作你都可以在字符串的任意位置插入任意字符。请你返回让 s 成为回文串的 最少操作次数 。「回文串」是正读和反读都相同的字符串。解题思路沿用原先的套路状态表示dp[i][j]表示i~j 这段字符串变为回文串所需的最少操作次数还是将字符串的长度分三种情况讨论当字符串两头的字符一样时①dp[i][j]0;②dp[i][j]0;③dp[i][j]dp[i1][j-1];既然前两种情况的dp值都为0那么在代码编写时可以直接不考虑它们让 j 直接从i1开始就行因为dp表的初始值就为0当字符串两头的字符不一样时可以在 i 的左边添加上s[j] 或 在 j 的右边添加上s[i]构造一个两头相同的字符串再检查此时去掉两头后中间的字符串就行了取这两种方法的最小操作次数即dp[i][j]Math.min(dp[i][j-1],dp[i1][j])1;代码实现及解析classSolution{publicintminInsertions(Strings){intns.length();int[][]dpnewint[n][n];//填表for(intin-1;i0;i--){for(intji1;jn;j){if(s.charAt(i)s.charAt(j)){//两头相同则看看中间那段的最小插入次数是多少就行了dp[i][j]dp[i1][j-1];//当为情况二时dp[i][j]得到的是一个dp表中没有用到的位置的值也就是0恰好符合答案}else{//两头不同则可以分别向两头添上另外一头的字符构造一个两头相同的字符串再检查此时中间的字符串就行了dp[i][j]Math.min(dp[i][j-1],dp[i1][j])1;}}}returndp[0][n-1];}}总结复习解题思路