首页 > itarticle > 5.longest_palindromic_substring 最长回文子串

5.longest_palindromic_substring 最长回文子串

admin 11月 13, 2020 0

Medium
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”

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：

输入: “cbbd”
输出: “bb”

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
 
class Solution {
    string helper(int l,int r, string &s){       
        while(l>=0 && r<s.length() && s[l] == s[r])
        {
            l
            r++;
        }
        return s.substr(l+1,r-l-1);
    }
public:
    string longestPalindrome(string s) {
        string res = "";
        for (int i = 0; i<s.length(); i++)
        { 
            string tempSubStr = helper(i,i,s);
            if (res.length() < tempSubStr.length())
            {
                res = tempSubStr;
            }
			
            tempSubStr = helper(i,i+1,s);
            if (res.length() < tempSubStr.length())
            {
                res = tempSubStr;
            }
        }      
        return res;
    }
};

相邻字符相同，判断连续相同字符左右两边是否对称

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
 
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.size();
        if (n <= 1)
            return s;
        int lindex = 0, rlen = 0;
        for (int i = 0; i < n - 1; i++)
        {//“扩张”法
            if (rlen >= (n - i) * 2)
                return s.substr(lindex, rlen);
            int count = 0;
            while (i < n - 1 && s[i + 1] == s[i])
            {//先判断index范围
                i++;
                count++;
            }
            int end = i;
            int first = i - count;
            while (first > 0 && end < n - 1 && s[first - 1] == s[end + 1])
            {
                first--;
                end++;
            }
            if (rlen < end - first + 1)
            {
                lindex = first;
                rlen = end - first + 1;
            }
        }
        return s.substr(lindex, rlen);
    }
};
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能