查找字符串最長回文

CastlePeaK 發布于2019-07-25 12:03 / 3315人閱讀

摘要：查找字符串最長回文思路回文有奇回文和偶回文，是奇回文，是偶回文回文都是中心對稱，找到對稱點后，同時向前后尋找回文的最長串即可奇回文和偶回文可以歸為同一種情況，即以為對稱點，以為對稱點，但為了代碼可讀性，可以分開討論代碼奇回文偶回文本題

查找字符串最長回文 Longest Palindromic Substring

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是奇回文，abccba是偶回文

回文都是中心對稱，找到對稱點后，同時向前后尋找回文的最長串即可

奇回文和偶回文可以歸為同一種情況，即abcba以c為對稱點，abccba以cc為對稱點，但為了代碼可讀性，可以分開討論

代碼

class Solution(object):

    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        self.maxlen = 0
        self.retstr = ""
        if len(s) < 2:
            return s
        for i in range(len(s)):
            self.__find_palindrome(s, i, i) #奇回文
            self.__find_palindrome(s, i, i+1) #偶回文
        return self.retstr


    def __find_palindrome(self, s, j, k):
        while j >= 0 and k < len(s) and s[j] == s[k]:
            j -= 1
            k += 1
        if self.maxlen < k - j + 1:
            self.maxlen = k - j + 1
            self.retstr = s[j+1:k]

本題以及其它leetcode題目代碼github地址: github地址

GPU云服務器云服務器回文字符串回文字符串算法c語言判斷回文字符c語言字符串查找函數

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/38654.html

[算法總結] 搞定 BAT 面試——幾道常見的子符串算法題

摘要：第一種方法常規方法。如果不存在公共前綴，返回空字符串。注意假設字符串的長度不會超過。說明本題中，我們將空字符串定義為有效的回文串。示例輸入輸出一個可能的最長回文子序列為。數值為或者字符串不是一個合法的數值則返回。說明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站點：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 評論0 收藏0
最長回文子串——Manacher 算法

摘要：問題定義最長回文子串問題給定一個字符串，求它的最長回文子串長度。可以采用動態規劃，列舉回文串的起點或者終點來解最長回文串問題，無需討論串長度的奇偶性。 0. 問題定義最長回文子串問題：給定一個字符串，求它的最長回文子串長度。如果一個字符串正著讀和反著讀是一樣的，那它就是回文串。下面是一些回文串的實例： 12321 a aba abba aaaa tatt...

mingzhong 2019-07-24 18:10 評論0 收藏0
獲取最長回文子串

摘要：以下是最長回文子串的相關代碼，相關邏輯已在注釋中注明我們原有的字符串可能存在兩種回文子串，一種是具有基數個元素例如一種是具有偶數個元素例如這樣的話分情況判斷比較復雜所以我們對原字符串進行擴充在相鄰元素中插入特殊值插入后的原基數回文子串變成了以下是最長回文子串的Manacher‘s Algorithm相關代碼，相關邏輯已在注釋中注明： public static String solu...

ymyang 2019-08-19 11:46 評論0 收藏0
Leetcode 5 Longest Palindromic Substring 最長回文子串

摘要：難度題目是說給出一個字符串求出這個字符串的最長回文的子串回文是指前后完全對稱的字符串像是之類的都算是回文奇數字母的回文和偶數字母的回文中心是不一樣的奇數字母比如的中心在中間字母上偶數字母比如的回文在中間兩字母的中心上由此可見回文中心點實際上 Given a string s, find the longest palindromic substring in s. You may as...

NotFound 2019-08-14 17:12 評論0 收藏0
LeetCode.5 最長回文子串(longest-palindromic-substring)(J

摘要：一題目最長回文子串給定一個字符串，找到中最長的回文子串。你可以假設的最大長度為。示例輸入輸出注意也是一個有效答案。一、題目最長回文子串：給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。示例 1：輸入: babad輸出: bab注意: aba 也是一個有效答案。示例 2：輸入: cbbd輸出: bb 二、我的答案思路 1.排...

Steven 2019-08-23 16:47 評論0 收藏0