题目

5. 最长回文子串

答案

方法一：暴力求解

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
class Solution {
public:
    std::string longestPalindrome(std::string s) {
        int len = s.size();
        if (len < 2) {
            return s;
        }
        
        int max_len = 1;
        int begin = 0;
        
        for (int i = 0; i < len - 1; ++i) {
            for (int j = i + 1; j < len; ++j) {
                if (j - i + 1 > max_len && validPalindromic(s, i, j)) {
                    max_len = j - i + 1;
                    begin = i;
                }
            }
        }
        
        return s.substr(begin, max_len);
    }

private:
    //判断字串是否为回文串
    bool validPalindromic(const std::string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
};

方法二：中心扩散

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
class Solution {
public:
    std::string longestPalindrome(std::string s) {
        int len = s.size();
        if (len < 2) {
            return s;
        }
        
        int max_len = 1;
        int begin = 0;
        
        for (int i = 0; i < len - 1; ++i) {
            int odd_len = expandAroundCenter(s,i,i);
            int even_len = expandAroundCenter(s,i,i+1);
            int cur_max_len = max(odd_len,even_len);
            if(cur_max_len > max_len)
            {
                max_len = cur_max_len;
                begin = i - (max_len-1)/2;
            }
        }
        return s.substr(begin, max_len);
    }

private:
    //中心扩散确定最长回文串长度
    int expandAroundCenter(const std::string& s, int left, int right) {
        int len = s.size();
        int i = left;
        int j = right;
        while(i>=0 && j<len)
        {
            if(s[i] == s[j])
            {
                i--;
                j++;
            }
            else
            {
                break;
            }
            
        }
        //跳出循环的条件为s[i]!=s[j]
        //长度为j-i+1-2,不包括当前i和j的位置
        return j-i-1;
    }
};

方法三：动态规划

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
class Solution {
public:
    std::string longestPalindrome(std::string s) {
        int len = s.size();
        if (len < 2) {
            return s;
        }
        
        int max_len = 1;
        int begin = 0;
        //动态规划用于存储字符串位置i至位置j是否为回文串
        bool dp[len][len];
        for(int i = 0;i<len;i++)
        {	
            //单个字符串的每个位置肯定为回文串
            dp[i][i]=true;
        }
        for(int j=1;j<len;j++)
        {
            for(int i= 0;i<j;i++)
            {
                //如果最左侧和最右侧不相等，那么就设置为false
                if(s[i]!=s[j])
                {
                    dp[i][j] = false;
                }
                else
                {
                    //如果相等且只有两个或三个字符那么直接为回文串
                    if(j-i<3){
                        dp[i][j]=true;
                    }
                    //如果相等且长度超过两个字符那么就取决于最左侧往右边移一格和最右侧往左边移一格是否为回文，是否回文与dp[i+1][j-1]相等
                    else{
                        dp[i][j]=dp[i+1][j-1];
                    }

                }
                //判断是否为为最大长度的回文串记录xia
                if(dp[i][j]&&j-i+1>max_len)
                {
                    max_len=j-i+1;
                    begin=i;
                }

            }
            
        }
        return s.substr(begin,max_len);
    }
};

__END__