给你一个字符串s，找到 s中最长的回文子串
https://leetcode-cn.com/problems/longest-palindromic-substring/
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd"
输出："bb"示例 3：
输入：s = "a"
输出："a"示例 4：
输入：s = "ac"
输出："a"
Java解法
思路：
待优化思路：
- 拆分为判断是否回文以及字符串遍历
能通过测试用例，但耗时较为严重public String longestPalindrome(String s) { if (s == null || s == "" || s.length() == 1) { return s; } String resultS = ""; for (int leftIndex = 0; leftIndex < s.length() - 1; leftIndex++) { int rightIndex = s.length(); if (rightIndex-leftIndex<resultS.length()) { break; } while (rightIndex > leftIndex) { String tempS = s.substring(leftIndex, rightIndex); if (isPalindrome(tempS.toCharArray())) { resultS = resultS.length() > tempS.length() ? resultS : tempS; break; } rightIndex--; } } return resultS; } public boolean isPalindrome(char[] chars) { if (chars == null) { return false; } int mid = chars.length / 2; for (int i = 0; i < mid; i++) { if (chars[i] != chars[chars.length - 1 - i]) { return false; } } return true; }
优化思路：参考官方解1
使用动态规划：回文串的去掉头尾必然是子串，所以在计算时依赖子串是不是回文来进行判断，具体思路看注释
动态规划原理 1. 基本思想： 问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，在构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。 2. 使用条件：可分为多个相关子问题，子问题的解被重复使用 - Optimal substructure（优化子结构）： - 一个问题的优化解包含了子问题的优化解 - 缩小子问题集合，只需那些优化问题中包含的子问题，降低实现复杂性 - 我们可以自下而上的 - Subteties（重叠子问题）：在问题的求解过程中，很多子问题的解将被多次使用。 3. 动态规划算法的设计步骤： - 分析优化解的结构 - 递归地定义最优解的代价 - 自底向上地计算优化解的代价保存之，并获取构造最优解的信息 - 根据构造最优解的信息构造优化解 4. 动态规划特点： - 把原始问题划分成一系列子问题； - 求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间 - 自底向上地计算。 - 整体问题最优解取决于子问题的最优解（状态转移方程）（将子问题称为状态，最终状态的求解归结为其他状态的求解）
package sj.shimmer.algorithm;
/**
* Created by SJ on 2021/1/28.
*/
class D4 {
public static void main(String[] args) {
System.out.println(longestPalindrome("babad"));
System.out.println(longestPalindrome("cbbd"));
System.out.println(longestPalindrome("a"));
System.out.println(longestPalindrome("ac"));
System.out.println(longestPalindrome("bb"));
}
public static String longestPalindrome(String s) {
if (s == null || s == "" || s.length() == 1) {
return s;
}
String resultS = "";
int n = s.length();
boolean[][] dp = new boolean[n][n];//用于记录比较过程结果,下标为字符串左右位置
for (int i = 0; i < n; i++) {
for (int left = 0; left+i < n; left++) {
int right = i+left;
if (i == 0) {//为0时，指向的都是一个字符，自然是回文
dp[left][right] = true;
} else if (i == 1) {//为1时，查找的是两个字符，自然是回文
dp[left][right] = (s.charAt(left) == s.charAt(right));
} else {//>1时，比较当前两之外，再比较一下内部上一次比较的子串结果
dp[left][right] = (s.charAt(left) == s.charAt(right) && dp[left + 1][right - 1]);
}
//比较成功时，判断当前的长度截取是否需要替换
if (dp[left][right] && i + 1 > resultS.length()) {
resultS = s.substring(left, right+ 1);
}
}
}
return resultS;
}
}
image
官方解
动态规划
上述使用-
中心扩展
针对回文字符串进行扩展尝试，扩展成功则记录最大值abcda(abccba)
- 分别对a、b...进行回文扩展尝试，若可以则记录(这样遍历出所有的奇数长回文字符串)
- 分别对ab、bc...进行回文扩展尝试，若可以则记录(这样遍历出所有的偶数长回文字符串)
- 取最大值
