查找字符串最長(zhǎng)回文

CastlePeaK 發(fā)布于2019-07-25 12:03 / 3375人閱讀

摘要：查找字符串最長(zhǎng)回文思路回文有奇回文和偶回文，是奇回文，是偶回文回文都是中心對(duì)稱，找到對(duì)稱點(diǎn)后，同時(shí)向前后尋找回文的最長(zhǎng)串即可奇回文和偶回文可以歸為同一種情況，即以為對(duì)稱點(diǎn)，以為對(duì)稱點(diǎn)，但為了代碼可讀性，可以分開(kāi)討論代碼奇回文偶回文本題

查找字符串最長(zhǎng)回文 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是偶回文

回文都是中心對(duì)稱，找到對(duì)稱點(diǎn)后，同時(shí)向前后尋找回文的最長(zhǎng)串即可

奇回文和偶回文可以歸為同一種情況，即abcba以c為對(duì)稱點(diǎn)，abccba以cc為對(duì)稱點(diǎn)，但為了代碼可讀性，可以分開(kāi)討論

代碼

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地址

云服務(wù)器 GPU云服務(wù)器回文字符串回文字符串算法c語(yǔ)言判斷回文字符c語(yǔ)言字符串查找函數(shù)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/38654.html

相關(guān)文章

[算法總結(jié)] 搞定 BAT 面試——幾道常見(jiàn)的子符串算法題

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

chanjarster 2019-08-19 11:07 評(píng)論0 收藏0
最長(zhǎng)回文子串——Manacher 算法

摘要：?jiǎn)栴}定義最長(zhǎng)回文子串問(wèn)題給定一個(gè)字符串，求它的最長(zhǎng)回文子串長(zhǎng)度?？梢圆捎脛?dòng)態(tài)規(guī)劃，列舉回文串的起點(diǎn)或者終點(diǎn)來(lái)解最長(zhǎng)回文串問(wèn)題，無(wú)需討論串長(zhǎng)度的奇偶性。 0. 問(wèn)題定義最長(zhǎng)回文子串問(wèn)題：給定一個(gè)字符串，求它的最長(zhǎng)回文子串長(zhǎng)度。如果一個(gè)字符串正著讀和反著讀是一樣的，那它就是回文串。下面是一些回文串的實(shí)例： 12321 a aba abba aaaa tatt...

mingzhong 2019-07-24 18:10 評(píng)論0 收藏0
獲取最長(zhǎng)回文子串

摘要：以下是最長(zhǎng)回文子串的相關(guān)代碼，相關(guān)邏輯已在注釋中注明我們?cè)械淖址赡艽嬖趦煞N回文子串，一種是具有基數(shù)個(gè)元素例如一種是具有偶數(shù)個(gè)元素例如這樣的話分情況判斷比較復(fù)雜所以我們對(duì)原字符串進(jìn)行擴(kuò)充在相鄰元素中插入特殊值插入后的原基數(shù)回文子串變成了以下是最長(zhǎng)回文子串的Manacher‘s Algorithm相關(guān)代碼，相關(guān)邏輯已在注釋中注明： public static String solu...

ymyang 2019-08-19 11:46 評(píng)論0 收藏0
Leetcode 5 Longest Palindromic Substring 最長(zhǎng)回文子串

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

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

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

Steven 2019-08-23 16:47 評(píng)論0 收藏0