目录
- LeetCode5.最长回文子串
- 问题
- 分析
- 解法一：中心扩散法
- 解法二：动态规划
- 解法三：马拉车算法
- 对原始字符串进行预处理（添加分隔符）
- 计算辅助数组p
- 代码实现
- 解法一：中心扩散法
- 解法二：动态规划
- 解法三：马拉车算法
LeetCode5.最长回文子串
问题
分析
解法一：中心扩散法
- 顾名思义就是每一个位置中心去扩散，去找回文串，遇到不是回文串的时候结束。
- 寻找方法就是首先先找其左边和右边位置，如果相等即继续走，只到走到左边的值和右边的值都不和中间元素相等，然后判断左右值是否相等。
解法二：动态规划
回看中心扩展算法，其实中间做了很多重复的计算，而动态规划就是为了减少重复计算的问题。即以空间换时间，将计算结果暂时存放起来，以避免重复计算
使用boolean dp[l] [r]表示字符串l到r这段是否是回文串，如果dp[l] [r]=true我们要判断dp[l-1] [r+1]是否是回文串只需要判断l-1和r+1两个位置的字符是否相同
- 关键是找到初始状态以及状态转移方程
- 初始状态：l=r此时dp[l] [r]=true
- 状态转移方程：dp[l] [r]=true并且（l-1）和（r+1）两个位置为相同的字符，此时dp[l-1] [r+1]=true
解法三：马拉车算法
马拉车算法本质上还是中心扩散法，只不过它使用了类似kmp算法的技巧，充分挖掘了已经镜像回文判定的子串的特点。在遍历的过程中，记录了已经遍历过的子串的信息。典型的以空间换时间。
对原始字符串进行预处理（添加分隔符）
- 即加入特殊字符，使得不用讨论奇偶情况，全是奇数情况。
- 新字符串的回文子串一定以分隔符作为两边的边界。
计算辅助数组p
辅助数组p记录了新字符串中以每个字符为中心的回文子串的信息，辅助数组p的对大致就是”最长回文子串“的长度。
另外在计算辅助数组p的过程中记录这个最大值。
代码实现
解法一：中心扩散法
public static String longestPalindrome(String s) {
if(s.length()<2){
return s;
}
int slen=s.length();
int ans=0;
int len=1;
int low=0;
int heigh=0;
int ansStart=0;
for(int i=1;i<slen;i++){
len=1;
low=i-1;
heigh=i+1;
while (low>=0&&s.charAt(low)==s.charAt(i)){
len++;
low--;
}
while (heigh<slen&&s.charAt(heigh)==s.charAt(i)){
len++;
heigh++;
}
while (low>=0&&heigh<slen&&s.charAt(low)==s.charAt(heigh)){
len+=2;
low--;
heigh++;
}
if(len>ans){
ans=len;
ansStart=low;
}
}
return s.substring(ansStart+1,ansStart+ans+1);
}
解法二：动态规划
public String longestPalindrome(String s) {
if (s == null || s.length() < 2) {
return s;
}
int strLen = s.length();
int maxStart = 0; //最长回文串的起点
int maxEnd = 0; //最长回文串的终点
int maxLen = 1; //最长回文串的长度
boolean[][] dp = new boolean[strLen][strLen];
for (int r = 1; r < strLen; r++) {
for (int l = 0; l < r; l++) {
if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
dp[l][r] = true;
if (r - l + 1 > maxLen) {
maxLen = r - l + 1;
maxStart = l;
maxEnd = r;
}
}
}
}
return s.substring(maxStart, maxEnd + 1);
}
