☆打卡算法☆LeetCode 5、最长回文子串 算法解析

> 推荐阅读

>

> - CSDN主页

> - GitHub开源地址

>- Unity3D插件分享

> - 简书地址

> - 我的个人博客

> - QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

## 一、题目

### 1、算法题目

“找到字符串中的最长回文串。”

题目链接：

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-palindromic-substring/

### 2、题目描述

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

比如：

> 输入：s = “babad”

> 输出：“bab”

> “aba” 同样符合题意。

## 二、解题

### 1、思路分析

这道题首先我想到用暴力法来解决题目，列举所有的字符串，判断是否为回文串，保存最长的回文串。

### 2、代码实现

用两层循环对每个子串进行检查，最后取最长的子串作为结果。

```csharp

public class Solution

{

​ //暴力解法:

​ public string LongestPalindrome(string s)

​ {

​ int maxLen = 0;

​ int begin = 0;

​ for (int left = 0; left < s.Length; left++)

​ {

​ for (int right = s.Length - 1; right >= 0; right–)

​ {

​ if (((right - left + 1) > maxLen) && VerifyPalindrome(s, left, right))

​ {

​ maxLen = right - left + 1;

​ begin = left;

​ }

​ }

​ }

​ return s.Substring(begin, maxLen);

​ }

​ // 验证回文子串

​ public bool VerifyPalindrome(string s, int left, int right)

​ {

​ while (left < right)

​ {

​ if (s[left] != s[right])

​ {

​ return false;

​ }

​ left++;

​ right–;

​ }

​ return true;

​ }

}

```

执行结果：

### 3、时间复杂度

时间复杂度： O(n³)

两层for循环O(n²)，for循环里面判断是否为回文O(n)，所以时间复杂度为O(n³)

空间复杂度： O(1)

有常数级个变量，所以空间复杂度为O(1)。

## 三、总结

暴力解法，时间复杂度： O(n²)，空间复杂度： O(1)，空间换时间。

可以考虑使用动态规划的方式，以空间换时间，可以将时间复杂度优化为O(n²)，但相应的空间复杂度会增大。

还可以使用中心扩展法，该方法对于该题目来说是一种比较适合的解决方法，时间复杂度为O(n²)，空间复杂度O(1)。

最后，还有一个Manacher马拉车算法，该算法利用了回文的特点，将时间复杂度降为了O(n)。