前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >专栏 >最长回文子串 -- 三种解答

最长回文子串 -- 三种解答

原创
作者头像
秦怀杂货店
修改2021-10-09 10:01:49
修改2021-10-09 10:01:49
2930
举报
文章被收录于专栏:技术杂货店技术杂货店

## 题目描述

给你一个字符串 s,找到 s 中最长的回文子串。

## 例子

```txt

示例 1:

输入:s = "babad"

输出:"bab"

解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd"

输出:"bb"

示例 3:

输入:s = "a"

输出:"a"

示例 4:

输入:s = "ac"

输出:"a"

```

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/longest-palindromic-substring,著作权归领扣网络所有。

## 思路以及解答

### 暴力破解

暴力破解,即是针对里面每一个子串,都去判断是否为回文串。

![](https://markdownpicture.oss-cn-qingdao.aliyuncs.com/blog/20210912143620.png)

判断每一个字符是不是回文串,比如用 `cbac` 判断,左右两个指针,对称判断,相等则往中间移动,继续判断,不相等则直接返回 false 。

![](https://markdownpicture.oss-cn-qingdao.aliyuncs.com/blog/20210912144540.png)

```java

public static String longestPalindrome(String s) {

if (s == null || s.length() == 0) {

return s;

}

String result = s.substring(0, 1);

for (int i=0; i < s.length() - 1; i++) {

for (int j = i + 1; j < s.length(); j++) {

if (judge(s, i, j) && j - i + 1 > result.length()) {

result = s.substring(i, j+1);

}

}

}

return result;

}

// 判断每个子串是不是回文

public static boolean judge(String source, int start, int end) {

// 对称轴对比

while (start <= end) {

if (source.charAt(start) != source.charAt(end)) {

return false;

}

start++;

end--;

}

return true;

}

```

暴力破解复杂度过高,会超时,不推荐使用。

![](https://markdownpicture.oss-cn-qingdao.aliyuncs.com/blog/20210912144801.png)

### 中心拓展法

回文串总是中心对称的,前面使用暴力法的时候,都是截取出子串之后再判断,只有判断到全部对称,才能证明回文,这样其实走了很多弯路,只要最后一个不对称,前功尽弃。

反过来想,我们不如在每一个点,都尝试往两边拓展,这样只要不匹配,就可以及时止顺。

![](https://markdownpicture.oss-cn-qingdao.aliyuncs.com/blog/20210912210151.png)

值得注意的是,中心拓展法的中心怎么找?3个字符有多少个中心呢?

![](https://markdownpicture.oss-cn-qingdao.aliyuncs.com/blog/20210912211149.png)

一共有五个中心,有些中心可能是两个字符的间隙,有些中心可能是字符。那么设计的时候,我们用 `left` 和 `right` 表示两个指针:

- `left = right`:对称中心为字符

- `left + 1 = right`: 对称中心为两个字符的间隙

具体实现如下:

```java

class Solution {

// 开始下标

public static int start = -1;

// 最大长度

public static int maxLen= 0;

public String longestPalindrome(String s) {

start = -1;

maxLen = 0;

if(s==null||s.length()==0){

return "";

}

for(int i=0;i<s.length();i++){

// 以当前字符为对称轴

judge(s,i,i);

// 以当前字符和下一个字符的间隙为对称轴

judge(s,i,i+1);

}

if(start == -1){

return "";

}

return s.substring(start,start+maxLen);

}

public void judge(String s,int left,int right){

while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){

left--;

right++;

}

int size = right-left-1;

if(size > maxLen){

maxLen = size;

start = left+1;

}

}

}

```

### 动态规划

其实,一个字符串是回文串的话,那么它倒过来读也是一样的,也就是说,它与它反转后的字符串,其实是完全匹配的,那么要是我们用一个字符串和它反转字符串一一统计匹配,是不是就可以得到结果呢?

答案是肯定的!假设原字符串为 `s1`,反转后的字符串为 `s2`,字符串长度为 `n`,我们用数组 `nums[n][n]` 来记录匹配的数量,`nums[i][j]`表示以 `s1[i]` 结尾的字符子串,和以 `s2[j]`结尾的字符子串,两者的匹配字符的最大数值。

- 当 `s1[i] == s2[j]`:

- 如果 `i == 0` 或者 `j == 0`: `nums[i][j] = 1`

- 否则 `nums[i][j] = nums[i - 1][j - 1] + 1;`

- 如果 `s1[i] != s2[j]`,则 `nums[i][j]=0`

前面说的其实就是状态转移表达式,也就是 `nums[i][j]` 是怎么求解的?`nums[i][j]` 是依赖于 `nums[i - 1][j - 1]` 和 当前字符是否匹配,如果当前字符不匹配,直接赋值为 0,只有在当前字符匹配的情况下,才会需要看前面一位的匹配数值 `nums[i - 1][j - 1]`。

假设以 `babad` 为例子:

![](https://markdownpicture.oss-cn-qingdao.aliyuncs.com/blog/20210913001730.png)

最后两行的计算:

![](https://markdownpicture.oss-cn-qingdao.aliyuncs.com/blog/20210913001823.png)

实现的代码如下:

```java

class Solution {

public static String longestPalindrome(String s) {

if (s == null || s.length() == 0) {

return "";

}

if (s.length() == 1) {

return s;

}

int len = s.length();

String s1 = new StringBuffer(s).reverse().toString();

int[][] nums = new int[len][len];

int end = 0, max = 0;

for (int i = 0; i < nums.length; i++) {

for (int j = 0; j < nums.length; j++) {

if (s1.charAt(i) == s.charAt(j)) {

if (i == 0 || j == 0) {

nums[i][j] = 1;

} else {

nums[i][j] = nums[i - 1][j - 1] + 1;

}

}

if (nums[i][j] > max) {

if (len - i - 1 + nums[i][j] - 1 == j) {

end = j;

max = nums[i][j];

}

}

}

}

return s.substring(end - max+1, end+1);

}

}

```

# 作者简介

**【作者简介】**:

秦怀,公众号【**秦怀杂货店**】作者,技术之路不在一时,山高水长,纵使缓慢,驰而不息。个人写作方向:`Java源码解析`,`JDBC`,`Mybatis`,`Spring`,`redis`,`分布式`,`剑指Offer`,`LeetCode`等,认真写好每一篇文章,不喜欢标题党,不喜欢花里胡哨,大多写系列文章,不能保证我写的都完全正确,但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处,还望指正。

[剑指Offer全部题解PDF](http://aphysia.cn/archives/jianzhiofferpdf)

[2020年我写了什么?](http://aphysia.cn/archives/2020)

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档