leetcode 005 最长回文子串

博主： zhaojun
发布时间：2023 年 02 月 02 日
1250 次浏览
暂无评论
1277字数
分类：默认分类

## 题目

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

**示例 1：**

**输入：** s = "babad"
**输出：**"bab"
**解释：**"aba" 同样是符合题意的答案。

**示例 2：**

**输入：** s = "cbbd"
**输出：**"bb"

**提示：**

-   `1 <= s.length <= 1000`
-   `s` 仅由数字和英文字母组成

## 思路

### 中心扩散法
中心扩散法，依次把字符串中每个字符当成中心，向左右扩散比对。将某个字符最大的扩散长度和开始长度记录下来，最后返回这个最大的扩散区间即可。

详细规则如下：
1. 循环 s 中每个字符作为中心，这个字符的下标定义为 i
2. 扩散初始状态
    1. 向左扩散 `left = i - 1`
    2. 向右扩展 `right = i + 1`
    3. `len = 1` 表示扩散长度默认为 1 (最少的回文字符就是 1，随便一个字符都可以认为是一个回文字符)
    4. `maxLen` 表示最大的扩散宽度，可能从下标 3 向两边扩散了 3 次，但从下标 5 可以向左右扩散6 次，所以要记录最大的扩散宽度。
    5. `maxStartIndex` 因为这道题不是让计算最大扩散宽度，还要返回整个回文字母，所以还要记录最大扩散的 left 值，是回文字符串的开始值。
3. 最后返回 `s.substring(maxStartIndex + 1, maxStartIndex + maxLen + 1)`。之所以要 +1 是因为 `maxStartIndex` 这个索引已经不包含回文字符了，它是回文字符的左边的那个索引。

### 动态规划
使用 `dp[l][r]` 表示从 `l` 到 `r` 这段是否是回文，如果 `dp[l][r] = true`，那么要判断 `dp[l - 1][r + 1]` 时，只需要判断  `l - 1` 和 `r + 1` 这两个位置的字符串是否是相等的即可。
例如 `str = "cabac"`，`l = 1`，`r = 3`，`dp[1][3]` 确定了是回文串时，只需要判断左右两个的 `l - 1 = 0` 与 `r + 1 = 4` 这两个位置的字符串是否相等。（大白话就是如果一个字符串是回文串，那么在其左右两个加一个相同的字符，那它还是回文串）。

状态转移方程，`dp[l][r]=true` 并且(`l-1`)和（`r+1`)两个位置为相同的字符，此时 `dp[l-1][r+1]=true`。

## 代码

### 中心扩散法
```java
class Solution {  
    public String longestPalindrome(String s) {  
        int strLength = s.length();  
        int left = 0;  
        int right = 0;  
  
        int len = 1;  
        int maxStartIdx = 0;  
        int maxLen = 0;  
  
        for (int i = 0; i < strLength; i++) {  
            left = i - 1;  
            right = i + 1;  
            while (left >= 0 && s.charAt(left) == s.charAt(i)) {  
                left--;  
                len++;  
            }  
            while (right < strLength && s.charAt(right) == s.charAt(i)) {  
                right++;  
                len++;  
            }  
  
            while (left >= 0 && right < strLength && s.charAt(left) == s.charAt(right)) {  
                left--;  
                right++;  
                len += 2;  
            }  
  
            if (len > maxLen) {  
                maxLen = len;  
                maxStartIdx = left;  
            }  
            len = 1;  
        }  
  
        return s.substring(maxStartIdx + 1, maxStartIdx + maxLen + 1);  
    }  
}
```

### 动态规划

```java
class Solution {
    public String longestPalindrome(String 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++) {
                // 1. s.charAt(l) == s.charAt(r) 表示当前 left 和 right 相等
                // 2. dp[l + 1][r - 1] 如果回文字符串左右加上两个一样的字符，那它还是个回文字符串.
                //    如 aba，左右各加一个 c，那它还是回文字符串，这里的左右各加一个 c 其实就是第一个判断
                // 3. r - l <= 2 表示如果的间距小于等于 2，就不用判断 l 和 r 之间的那个子字符串是否是回文字符串了
                //    如 daac, l = 1, r = 2 时，条件 1 满足，但 r - l 为 1，这时候就不用判断条件 2 了，因为没有更小的子串了
                //       0123
                //    如 dabac, l = 1, r = 3 时，条件 1 满足，但 r - l 为 2，这时候也不用判断条件 2，因为 dp[l + 1][r - 1] 其实判断的是同一个字符(在这里 l  = 1, r = 3, l + 1 = 2, r - 1 = 2). 肯定会相等也不用判断.
                //       01234
                if (s.charAt(l) == s.charAt(r) && (dp[l + 1][r - 1] || r - l <= 2)) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxStart = l;
                        maxEnd = r;
                        maxLen = r - l + 1;
                    }
                }
            }
        }

return s.substring(maxStart, maxEnd + 1);
    }
}
```

最后修改：2023 年 02 月 02 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

天天下载
学习了，谢谢 http://appdo...
聊应用
来留个脚印。
快帆云
你好，我们的机场：快帆云，已经稳定运营三年多，现在诚邀推广员。...
在nginx层面给任意项目站点增加访问限制：casdoor+oauth2-proxy - Blog By chenchen.site
[...]如果是宝塔用户可以直接使用以下方法安装模块，参考文章...
大概
你好，我就想整一个网盘，用作知识付费，就是普通用户只可以看到标...

leetcode 005 最长回文子串

zhaojun • 2023 年 02 月 02 日

## 题目

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

**示例 1：**

**输入：** s = "babad"
**输出：**"bab"
**解释：**"aba" 同样是符合题意的答案。

**示例 2：**

**输入：** s = "cbbd"
**输出：**"bb"

**提示：**

-   `1 <= s.length <= 1000`
-   `s` 仅由数字和英文字母组成

## 思路

状态转移方程，`dp[l][r]=true` 并且(`l-1`)和（`r+1`)两个位置为相同的字符，此时 `dp[l-1][r+1]=true`。

## 代码

### 动态规划

boolean[][] dp = new boolean[strLen][strLen];

return s.substring(maxStart, maxEnd + 1);
    }
}
```

leetcode 005 最长回文子串

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

剑指 Offer 04. 二维数组中的查找

Shiro 学习 04 - 加密

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

leetcode 231 2 的幂

阿里云 Centos7.x 安装 Oracle 11g 详细过程

巧用 MyBatis 构建树形结构

debian 11 vps 安装 pve7

leetcode 303 区域和检索 - 数组不可变

leetcode 005 最长回文子串

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

leetcode 005 最长回文子串

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款