蜗牛慢慢爬 LeetCode 5.Longest Palindromic Substring [Difficulty: Medium]

题目

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

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

翻译

回文字符串即类似 abcba 正读和逆序读是一样的字符串

本题要求最长回文字符子串

Hints

Related Topics: String

回文字符串可以通过递归的方法判断一开始想到的是通过将原字符串倒置（reverse）然后求两个字符串的最大公共子串即是最大回文字符串但是失策了如果出现类似 abcdfrcba 就会将 abc 判断为回文字符串（囧）

所以还是遍历字符串追踪最长回文字符串的长度每遍历时增加一个字符那么 maxlen 可能加1或者加2 但不可能加3 所以只需要检查以该字符结尾往前的 maxlen(意味着可能加1) 或者 maxlen-1(意味着可能加2) 个字符组成的字符串是否是回文字符串

至于为什么不能加3 证明如下：

如果现在的maxlen=3 现在遍历到字符 a

1. 我们检查 ×××a 如果是回文字符串 maxlen+1 = 4

2. 我们检查 ××××a 如果是回文字符串 maxlen+2 = 5

3. 不检查 xxa 这样回文字符串长度没有增加

4. 不检查 ×××××a 因为如果它是回文字符串 那么必是 a××××a 中间的 ×××× 也是回文字符串 maxlen 是 4 而不是 3

代码

Java

//原理是相同的

class Solution {

    int maxlen, lo;

    public String longestPalindrome(String s) {

        int len = s.length();

        if(len<2)   return s;

        for(int i=0;i<len-1;i++){

            extendPalindrome(s, i, i);

            extendPalindrome(s, i, i+1);

        }

        return s.substring(lo,lo+maxlen);

    }

    public void extendPalindrome(String s,int start, int end){

        while(start>=0 && end<s.length() && s.charAt(start)==s.charAt(end)){

            start--;

            end++;

        }

        if(maxlen<end-start-1){

            lo = start+1;

            maxlen = end-start-1;

        }

    }

}

Python

class Solution(object):

    def judge(self, s, start, end):

        if start<0: return False

        while start<end:

            if s[start]==s[end]:

                start += 1

                end -= 1

            else:

                return False

        return True

    def longestPalindrome(self, s):

        """

        :type s: str

        :rtype: str

        """

        maxlen = 0

        res = ''

        for i in range(len(s)):

            if self.judge(s, i-maxlen-1, i):

                res = s[i-maxlen-1:i+1]

                maxlen += 2

            elif self.judge(s, i-maxlen,i):

                res = s[i-maxlen:i+1]

                maxlen += 1

        return res

巴特西

蜗牛慢慢爬 LeetCode 5.Longest Palindromic Substring [Difficulty: Medium]

题目

翻译

Hints

代码

Java

Python

最新文章

热门文章