19.1.20 [LeetCode 5]Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         int leng = 0, size = s.length();
 5         string p;
 6         for (int i = 0; i<size; i++) {
 7             int l = 1;
 8             int S = i, E = i;
 9             while (S > 0 && E < size - 1 && s[S - 1] == s[E + 1]) {
10                 S--, E++;
11                 l += 2;
12             }
13             if (l > leng) {
14                 p = s.substr(S, l);
15                 leng = l;
16             }
17         }
18         for (int i = 0; i < size-1; i++) {
19             if (i + 1 > size - 1)break;
20             int l = 0;
21             int S = i+1, E = i;
22             while (S > 0 && E < size - 1 && s[S - 1] == s[E + 1]) {
23                 S--, E++;
24                 l += 2;
25             }
26             if (l > leng) {
27                 p = s.substr(S, l);
28                 leng = l;
29             }
30         }
31         return p;
32     }
33 };

View Code

从大小为1或2的回文串开始扩展

注定失败的战争，也要拼尽全力去打赢它；就算输，也要输得足够漂亮。