Vintion's blog

~夜黑路滑，社会复杂~

Longest Palindromic Substring

| Comments

Longest Palindromic Substring
Probles

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

看本站内的总结：最长回文字符串

Code
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

class Solution {
public:
    string longestPalindrome(string s)
    {
        int len = s.length();
        string str="";
        if(len==0)return str;
        int maxlen = 0;
        int leng;
        int left,right;
        for(int i=0;i<2*len-1;i++)
        {
            if(i%2==0)
            {
                leng = 1;
                left = i/2 - 1;
                right = i/2 + 1;
                while(left>=0&&right<len&&s.at(left)==s.at(right))
                {
                    leng += 2;
                    left--;
                    right++;
                }
                 if(leng>maxlen)
              {
                    maxlen = leng;
                    str = s.substr(i/2-maxlen/2, maxlen);
              }
            }
            else
            {
                leng = 0;
                left = i/2;
                right = i/2+1;
                 while(left>=0&&right<len&&s[left]==s[right])
                {
                    leng += 2;
                    left--;
                    right++;
                }
               
            
             if(leng>maxlen)
              {
                    maxlen = leng;
                    str = s.substr(i/2-maxlen/2+1, maxlen);
              }
            }
        }
        return str;
    }
};
注意
    1. 把奇偶统一起来，这样i的大小是2len-1的大小
    1. 还有一个注意点是，substr()这个两个参数是指起始和长度，起始从0开始就算第一个
    1. 后面两个if判断不能统一起来，因为substr中的参数不一样
    1. 方法：从中间向两边比较来判断是否回文，例a_b_c_b_a，则这个字符串abcba长度5，判断的位置有9个，然后从中间向两边展开，首先判断是否出界，再看是不是相等，这样最后更新长度和字符串
  • 5.　本文属于最系列的应用

Comments