此文章用于记录有关回文子串的的题目
5. 最长回文子串
剑指 Offer II 027 回文链表
234. 回文链表
剑指 Offer II 018 有效的回文
125. 验证回文串
5. 最长回文子串
【题目描述】
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：
- 1 <= s.length <= 1000
- s 仅由数字和英文字母组成
动态规划
- 回文串两边加上两个相同字符，会形成一个新的回文串
- 方法是，建立二维数组 dp ，找出所有的回文子串。dp[i][j] 记录子串 i…j 是否为回文串
- 首先，单个字符就形成一个回文串，所以，所有 dp[i][i] = true
- 如果字符 s[i] 和 s[j] 相等，并且子串 i+1…j-1 是回文串的话，子串 i…j 也是回文串。
也就是，如果 s[i] == s[j] 且 dp[i+1][j-1] = true 时，dp[i][j] = true
- 要注意边界情况，即 子串 i+1…j-1 的有效性 ，当 i+1 <= j-1 时，它才有效
- 如果不满足，此时 j <= i+1 ，也就是子串 i…j 最多有两个字符， 如果两个字符 s[i] 和 s[j] 相等，那么是回文串
- 可以通过一个表格，来理解整个 dp 数组的规划过程
上面的表格填表过程： - 初始化所有方格写 false 。
- 填写对角线写 true 。
- 自对角线右下角开始，自下而上、自左而右，按箭头方向根据递推关系填表
【AC代码】
class Solution {
public String longestPalindrome(String s) {
if (s.length() <= 1)
return s;
char[] chArr = s.toCharArray();
int len = chArr.length;
boolean[][] dp = new boolean[len][len];
// 对角线初始化
for (int i = 0; i < len; i++) dp[i][i] = true;
int max_length = 1;
int index_l = 0;
for(int i = len - 1;i >=0; i--){
for(int j = i ;j < len ;j++){
// 如果相等
if (chArr[i] == chArr[j]) {
// 满足条件，如果前面 一个是回文串，那么这个就是回文
if(j - 1 >= i + 1){
dp[i][j] = dp[i + 1][j - 1];
}else{
dp[i][j] = true;
}
}
if(dp[i][j]){
int length = j - i + 1;
if(length > max_length){
// 记录最大的索引和长度
index_l = i;
max_length = length;
}
}
}
}
return new String(chArr,index_l ,max_length);
}
}
manacher（马拉车）
【思路】
- 由于回文分为偶回文（比如 abab 长度为4）和奇回文（比如 abcba 长度为5），而在处理奇偶问题比较麻烦，所以这里需要做 个预处理，在字符间插入一个特殊字符（这个字符不能在串里出现），将原串转换统一成奇串
- 比如原字符串： s =”abbaTNTabcba” => 插入字符之后：sNew= “$#a#b#b#a#T#N#T#a#b#c#b#a#”
- 算法需要一个与新串sNew等长的辅助数组int[] p，其中p[i]表示以sNew[i]为中心的最长回文子串的半径， 若p[i]=1，则该回文子串就是sNew[i]本身
Manacher算法利用开头提到的回文的左边是右边的镜像，让回文串起始的对比位置尽可能的大。
图注：id为已知的最大回文子串中心的位置，mx是已知最大回文串的右边界，i为当前遍历到字符串的位置
一、mx > i
二、mx < i
此时镜像对预判位置起不到作用，只能从长度为1开始对比，所以p[i] = 1。
【AC代码】
class Solution {
/**
* 最长回文子串 manacher
* @param s
* @return
*/
public String manacher(String s){
String str = init(s);
int len = str.length();
int mx = 0;
int id = 0;
int ans = -1;
int[] p = new int[len];
int index = 0;
for(int i = 2;i < len;i++){
if(i < mx){
p[i] = Math.min(mx - i,p[id * 2 - i]);
}else{
p[i] = 1;
}
while (str.charAt(i + p[i] - 1) == str.charAt(i - p[i] - 1)){
p[i]++;
}
if(p[i] + i > mx){
mx = p[i] + i;
id = i;
}
if(ans < p[i] - 1){
ans = p[i] - 1;
index = i;
}
}
String resStr = str.substring(index - p[index],index + p[index] - 1);
String res = "";
for (int i = 0; i < resStr.length(); i++) {
if(resStr.charAt(i) != '@' && resStr.charAt(i) != '#'){
res += resStr.charAt(i);
}
}
return res;
}
public String init(String str){
StringBuffer res = new StringBuffer("@#");
for (int i = 0; i < str.length(); i++) {
res.append(str.charAt(i));
res.append("#");
}
res.append('%');
return res.toString();
}
}
剑指 Offer II 027. 回文链表、234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
- 链表中节点数目在范围[1, 105] 内
- 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
【解题思路】
1、把链表的数字存入数组中，然后首尾双指针遍历判断
2、把链表存入字符串中，反转，然后equals比较
【AC代码】
class Solution {
// 方法一
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<Integer>();
// 将链表的值复制到数组中
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
// 使用双指针判断是否回文
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
// 方法二
public boolean isPalindrome(ListNode head) {
String s1 = "";
while (head != null){
s1 += head.val;
head = head.next;
}
StringBuffer buffer = new StringBuffer(s1);
return s1.equals(buffer.reverse().toString());
}
}
剑指 Offer II 018 有效的回文、125. 验证回文串
【题目描述】
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
示例 2:
输入: "race a car"
输出: false
解释："raceacar" 不是回文串
提示：
- 1 <= s.length <= 2 * 10^5
- 字符串 s 由 ASCII 字符组成
【思路】
- 先把有效的字符组合，然后通过双指针来判断是否回文
【AC代码】
class Solution {
public boolean isPalindrome(String s) {
int length = s.length();
StringBuffer str = new StringBuffer();
for (int i = 0; i < length; i++) {
if((s.charAt(i) >= 'a' && s.charAt(i) <= 'z') || (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') || (s.charAt(i) >= '0' && s.charAt(i) <= '9')){
str.append(s.charAt(i));
}
}
String s1 = str.toString();
String s2 = s1.toUpperCase();
int l = 0 ,r = s2.length() - 1;
while (l <= r){
if(s2.charAt(l) == s2.charAt(r)){
l++;
r--;
continue;
}else{
return false;
}
}
return true;
}
}
