查找字符串最长回文

CastlePeaK 发布于2019-07-25 12:03 / 3294人阅读

摘要：查找字符串最长回文思路回文有奇回文和偶回文，是奇回文，是偶回文回文都是中心对称，找到对称点后，同时向前后寻找回文的最长串即可奇回文和偶回文可以归为同一种情况，即以为对称点，以为对称点，但为了代码可读性，可以分开讨论代码奇回文偶回文本题

查找字符串最长回文 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语言字符串查找函数

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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