LeetCode 5. Longest Palindromic Substring(字符串)
LeetCode 5 Longest Palindromic Substring字符串
问题描述解题思路参考代码
By ScarbScarb’s Blog
Tags: - String
问题描述
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"
解题思路
遍历字符串的每一位，对每一位从中间展开，寻找该位(或者该位和下一位相同的情况就找该位和下一位)为中心的最长回文字符串。
参考代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
string longestPalindrome(
string s) {
int start =
0, end =
0;
for (
int i =
0; i < s.length(); ++i)
{
int len1 = expandFromCenter(s, i, i);
int len2 = expandFromCenter(s, i, i +
1);
int len = max(len1, len2);
if(len > end - start +
1)
{
start = i - (len -
1) /
2;
end = i + len /
2;
}
}
return s.substr(start, end - start +
1);
}
private:
int expandFromCenter(
string s,
int left,
int right)
{
int L = left, R = right;
while (L >=
0 && R < s.length() && s[L] == s[R])
{
--L;
++R;
}
return R - L +
1 -
2;
}
};
int main()
{
string test =
"babad";
auto sl =
new Solution();
cout << sl->longestPalindrome(test) << endl;
system(
"pause");
return 0;
}
