最长回文字符串

要求

给定一个字符串，求它的最长回文子字符串

做法

最长回文字符串的长度可能为奇数，也可能为偶数，所以我们可以假定这两种情况来求。我们采用中间拓展法来获取回文子串：由一个字符向它的左右两边拓展，当左右相等时继续拓展，当不等时停止拓展，记录此时的长度n，获得一个n长度的回文子串。然后对下一个字符继续用中间拓展法。当遍历完字符串所有字符后，选取长度最大的回文子串。

代码实现

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <string>
using namespace std;
class Solution {
public:
    string longestPalindrome(string s) {
        int n = (int)s.length();
                if (n==1) {
            return s;
        }
      //记录最长的回文子串长度
        int max = 0;
        int maxLeft = 0;
        int maxRight = 0;
        for(int i=0;i<n;i++){
          //假定回文子串的长度为奇数
            int start = i-1;
            int end = i+1;
            int len = 1;
            int left = start;
            int right = end;
            while (start>=0&&end<n) {
                if (s[start]==s[end]) {
                    len = len+2;
                    left = start;
                    right = end;
                    start--;
                    end++;
                }else{
                    break;
                }
            }
            if (len>max) {
                max = len;
                maxLeft = left;
                maxRight = right;
            }
            //假定回文子串的长度为偶数
            start = i;
            end = i+1;
            len = 0;
            left = start;
            right = end;
            while (start>=0&&end<n) {
                if (s[start]==s[end]) {
                    len = len+2;
                    left = start;
                    right = end;
                    start--;
                    end++;
                }else{
                    break;
                }
            }
            if (len>max) {
                max = len;
                maxLeft = left;
                maxRight = right;
            }
        }
        return s.substr(maxLeft,maxRight-maxLeft+1);
    }
};

Comments