【LeetCode】5.最长回文子串

Author： Traceless
发布时间：October
1253 views
No comments
3942 words
Categories：技术分享 LeetCode

# [最长回文子串](https://leetcode-cn.com/problems/longest-palindromic-substring/description/ "https://leetcode-cn.com/problems/longest-palindromic-substring/description/")

| Category | Difficulty | Likes | Dislikes |
| - | - | - | - |
| algorithms | Medium (30.98%) | 2816 | - |

[`string`](https://leetcode.com/tag/string "https://leetcode.com/tag/string") | [`dynamic-programming`](https://leetcode.com/tag/dynamic-programming "https://leetcode.com/tag/dynamic-programming")

</details>

给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。

**示例 1：**

```
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
```

**示例 2：**

```
输入: "cbbd"
输出: "bb"
```

---

[Discussion](https://leetcode-cn.com/problems/longest-palindromic-substring/comments/ "https://leetcode-cn.com/problems/longest-palindromic-substring/comments/") | [Solution](https://leetcode-cn.com/problems/longest-palindromic-substring/solution/ "https://leetcode-cn.com/problems/longest-palindromic-substring/solution/")

## 读题

首先理解“回文”概念：
**正着读反着读都一样的字符串**
用几何的角度来说就是，对称
那么对称都会有对称轴，思路就来了，一对称轴为中心，依次向两边扩散
**leetcode上的大佬称之为 中心扩散法**

## 解题

我们提到了中心扩散，但是有一个问题
奇数对称和偶数对称是不一样的，奇数时，对称轴是一个字母如"aba"，对称轴是"b"
而"abba"对称轴是两个"b"中间的空隙！
不纠结，拆成两个方法

### 奇数判断

```C#
public string findSignlePalind(string rawStr, int index, int nowMax)
{
    //处理"a"这种单个字符的字符串，也是回文
    if(rawStr.Length < 2) return rawStr;
    //最后偏移量
    var finalOffset = 0;
    //转char数组，比每次substring效率高
    var charArr = rawStr.ToCharArray();
    for(var offset = 1;; offset++)
    {
        //数组越界检查
        if(index - offset < 0 || index + offset >= rawStr.Length) break;
        //对称轴左字符
        var leftChar = charArr[index - offset];
        //对称轴右字符
        var rightChar = charArr[index + offset];
        if(leftChar == rightChar)
        {
            //相同，继续偏移
            finalOffset = offset;
            continue;
        }
        break;
    }
    //计算起始位置
    var left = index - finalOffset;
    //获取最终字符串
    return rawStr.Substring(left, finalOffset * 2 + 1);
}
```

### 偶数判断

```C#
public string findDoublePalind(string rawStr, int index, int nowMax)
{
    //处理"a"这种单个字符的字符串，也是回文
    if(rawStr.Length < 2) return rawStr;
    //最后偏移量
    var finalOffset = 0;
    //转char数组，比每次substring效率高
    var charArr = rawStr.ToCharArray();
    //记录是否有结果
    var hasRes = false;
    for(var offset = 0;; offset++)
    {
        //数组越界检查
        if(index - offset < 0 || index + offset + 1 >= rawStr.Length) break;
        //"abba"这种情况，把对称轴左边的字符当做对称轴
        //取左字符
        var leftChar = charArr[index - offset];
        //取右字符
        var rightChar = charArr[index + offset + 1];
        if(leftChar == rightChar)
        {
            //相同，继续偏移
            finalOffset = offset;
            hasRes = true;
            continue;
        }
        break;
    }
    if(!hasRes) return "";
    //计算起始位置
    var left = index - finalOffset;
    //获取最终字符串
    return rawStr.Substring(left, 2 * finalOffset + 2);
}
```

### 主程序逻辑

```C#
public string LongestPalindrome(string s)
{
    //记录最大长度
    int nowMax = 0;
    //记录最大字符串
    string nowStr = "";
    for(int i = 0; i < s.Length; i++)
    {
        //奇数回文查找
        string singleStr = findSignlePalind(s, i, nowMax);
        if(singleStr.Length > nowMax)
        {
            nowMax = singleStr.Length;
            nowStr = singleStr;
        }
        //偶数回文查找
        string doubleStr = findDoublePalind(s, i, nowMax);
        if(doubleStr.Length > nowMax)
        {
            nowMax = doubleStr.Length;
            nowStr = doubleStr;
        }
    }
    return nowStr;
}
```

### 思考

查看leetcode大佬们的解题思路，竟然还有“马拉车”方案，可以神奇地将时间复杂度拉到O(n)！可以借鉴学习一下，属于进阶大佬级别！

**仔细思考，其实可以使用双指针对奇偶两种情况进行统一，减少至少一半的不必要重复操作。具体修改 下回分解（那就不知道是啥时候了）**

### 膜拜大佬

如果大佬们有更好的解法，不如评论分享赐教~
[我的Leetcode解题代码库][1]

[1]: https://github.com/traceless0929/.leetcode

Last modification：October

如果觉得我的文章对你有用，请随意赞赏

【LeetCode】5.最长回文子串

Traceless • 2020 年 10 月 20 日

# [最长回文子串](https://leetcode-cn.com/problems/longest-palindromic-substring/description/ "https://leetcode-cn.com/problems/longest-palindromic-substring/description/")

| Category | Difficulty | Likes | Dislikes |
| - | - | - | - |
| algorithms | Medium (30.98%) | 2816 | - |

[`string`](https://leetcode.com/tag/string "https://leetcode.com/tag/string") | [`dynamic-programming`](https://leetcode.com/tag/dynamic-programming "https://leetcode.com/tag/dynamic-programming")

</details>

给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。

**示例 1：**

```
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
```

**示例 2：**

```
输入: "cbbd"
输出: "bb"
```

---

## 读题

## 解题

### 奇数判断

### 偶数判断

### 主程序逻辑

### 思考

查看leetcode大佬们的解题思路，竟然还有“马拉车”方案，可以神奇地将时间复杂度拉到O(n)！可以借鉴学习一下，属于进阶大佬级别！

**仔细思考，其实可以使用双指针对奇偶两种情况进行统一，减少至少一半的不必要重复操作。具体修改 下回分解（那就不知道是啥时候了）**

### 膜拜大佬

如果大佬们有更好的解法，不如评论分享赐教~
[我的Leetcode解题代码库][1]

[1]: https://github.com/traceless0929/.leetcode

【LeetCode】5.最长回文子串

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【小T】更新日志

【手摸手系列】教你开发QQ机器人 - 基础框架搭建

【手摸手系列】教你开发QQ机器人 - 目录导航

【手摸手系列】教你开发QQ机器人 - HTTP接口使用

【LeetCode】4.寻找两个正序数组的中位数

【手摸手系列】教你开发QQ机器人 - 基础框架搭建

【LeetCode】1.两数之和

【手摸手系列】教你开发QQ机器人 - HTTP接口使用

【LeetCode】2.两数相加

【手摸手系列】教你开发QQ机器人 - 目录导航

【LeetCode】5.最长回文子串

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【LeetCode】5.最长回文子串

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款