最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2： 输入: "cbbd" 输出: "bb"
仿No.4切入
- 回文序列本质上还是一个切割问题
- 以切割点为起始,逐步比较两边是否相等即可判断回文.
- 注意切割处可以是数, 也可以是两数之间
求解代码
题目思路较为简单,直接放出一遍撸过的代码. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35class Solution {
public:
string longestPalindrome(string s)
{
string result;
int center;
int left;
int right;
if (s.length() == 0)
return "";
//参考题4扩展
//[1,2,3] [1,# ,2,#,3]
//[2,1,1,2] [2,# ,1,#,1,#,2]
for (center = 0; center < 2*s.length()-1; center++)
{
left = center / 2;
right = (center + 1) / 2;
while (1)
{
if (left < 0 || right = s.length() || s[left] != s[right])
{
left++;
right--;
break;
}
left--;
right++;
}
if (right - left + 1 result.length())
result.assign(s, left, right - left + 1);
}
return result;
}
};