5. Longest Palindromic Substring （Medium）

2019-11-06 08:41:34

字体：大中小

来源：转载

供稿：网友

原题目：　　Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. 　　Example: 　　Input: “babad” 　　Output: “bab” 　　Note: “aba” is also a valid answer.

　　Example: 　　Input: “cbbd” 　　Output: “bb”

题目大意如下：　　从一个string中找到其最长的回文子串。

解题思路：　　回文：正读和反读都相同的字符序列为“回文”。　　例如：　　123321，aaaa，aba等等　　　　首先，我们注意到具有重复字符的子串部分一定是回文。　　然后，如果一个字符串是回文那么它必定从中间开始左右是对称的。　　所以我们遍历整个字符串，对于每个字符i进行扩展：（设r为当前字符i的下一个字符，l为当前字符的前一个字符，初始时i == r == l）　　①若s[r] == s[r + 1] ，当r < s.size() - 1，即往右拓展时有重复字符时，++r ；　　②若s[r] == s[l]，即符合“对称”条件时，++r且- -l ；　　③记录下区间长度（r - l + 1）和起始坐标start_index == l ，返回子串即可。　　第一第二种情况我们分别用一个while循环即可。　　注：我们并不需要往左拓展时检查有无重复字符，因为我们最外层的遍历是从左到右的。

代码如下：

class Solution {public: string longestPalindrome(string s) { if(s.empty()) return s ; if(s.size() == 1) return s ; int i = 0 ; int max_len = 0 , start_index ; //最外层循环遍历字符串 while(i < s.size()){ int l = i , r = i ; //先确定有无重复的字符 while(r < s.size() - 1 && s[r + 1] == s[r] ) ++r ; //while(l > 0 && s[l - 1] == s[l] ) --l ; //往左右进行扩展 while(l > 0 && r < s.size() - 1 && s[l - 1] == s[r + 1]){ --l ; ++r ; } //记录下区间长度和起始坐标 if( (r - l + 1) > max_len){ max_len = r - l + 1 ; start_index = l ; } ++i ; } return s.substr(start_index , max_len) ; }};

运行结果：