专栏首页用户6811391的专栏Python 版 LeetCode 刷题笔记 #5 无重复字符的最长子串(上)

Python 版 LeetCode 刷题笔记 #5 无重复字符的最长子串(上)

从下午三点半到晚上十二点,一直卡在这个题,郁闷。经过好几番尝试后,用暴力法完成并提交了一版代码,测试结果超出时间限制。根据反馈的测试用例,专门针对特例做了下处理,才勉强通过测试。

在优化时,参考推荐的“马拉车算法”(Manacher 算法),真的是深深的挫败感。原本盘算着消化理解后再来完成这篇文,奈何琢磨大半天了还没全弄明白。没辙,先记下,后续再慢慢消化吧。

题目

中文题目

第 5 题 无重复字符的最长子串:

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

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

输入: "cbbd"
输出: "bb"

英文题目

Question 5 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.

Input: "cbbd"
Output: "bb"

思路

最初我是觉得暴力、遍历循环这样解决肯定是不可取的,但是琢磨半天也没能想到好方法,只好就按照回文的规则来逐个暴力尝试了。

其中遇到比较烦恼的点是当重复字符出现在回文中间时,很容易就会破坏设计的规则。所以我决定先把位于子串最中心的重复字符给拿到。比如 "abbcccbba" 中,我要把最中心的 "ccc" 坐标拿到,这样向左、向右来逐个字符检测,直到到头、或者两边字符不匹配。

我是对每个字符遍历,先判断该字符后续有无连续出现相同字符,如果有的话把重复出现的字符合并,然后假定该字符为回文中心点,向左向右检测是否相同来生成以该字符为中心的最长回文串,最终来返回最长的结果。

代码

class Solution:
    def longestPalindrome(self, s: str) -> str:
        l = len(s)
        dic = {}
        result = {}
        # 获取字符串中每个字符所出现过的坐标
        for i,c in enumerate(s):
            dic.setdefault(c,[]).append(i)
        #print(dic)

        # 遍历字符串
        for i,c in enumerate(s):
            # start 为该字符左侧坐标
            start = i-1
            # start 为该字符右侧坐标
            ending = i+1
            # 如果左右两侧与该字符相同,将左右两侧的坐标更新
            while start in dic[c]:
                start -= 1
            while ending in dic[c]:
                ending += 1
            # 将该重复字符串添加到结果中
            result[i]=s[start+1:ending]

            # 对左右两侧的字符进行比较
            while start>-1 and ending<l:
                if s[start]==s[ending]:
                    # 如果两侧字符相同,更新结果中回文字符的记录
                    result[i]=s[start:ending+1]
                else:
                    break
                start-=1
                ending+=1
        #print(result)

        # 对我们记录所有回文字符串的 result 字典进行遍历,拿到最长的结果返回
        max_l = 0
        output = s[0] if len(s)>0 else ""
        for k,v in result.items():
            max_l = len(v) if len(v)>max_l else max_l
            if max_l == len(v):
                output = v

        return output

提交答案

提交答案后,结果是“超出时间限制”,原因是有个测试用例是拿长度为 1000的 "bbb…b" 来做的测试,结果我代码运行时间太长了。我在自己的代码中尝试对这个字符串进行处理,是可以拿到正确结果的,只是时间久了些。为了让代码通过,我专门对这种全重复字符的字符串进行额外处理:

# 将该字符串转化为集合
c_set = set(s)
# 如果集合中只有一个元素,直接返回这个字符串
if len(c_set)==1:
    return s

有了这个单独处理,勉强通过了测试。

中文区结果:

执行用时 :9856 ms ms, 在所有 Python3 提交中击败了5.04%的用户 内存消耗 :14.2 MB, 在所有 Python3 提交中击败了15.00%的用户

英文版结果:

Runtime: 8220 ms, faster than 6.10% of Python3 online submissions for Longest Palindromic Substring. Memory Usage: 14.3 MB, less than 17.65% of Python3 online submissions for Longest Palindromic Substring.

意料之中,在尝试了几个其它思路后,投降,开始翻看评论区中的 Manacher 算法。但直到现在也没能完全吃透。

结论

第五题,暴力破解法仍有提升空间,推荐的专门针对回文的马拉车算法也还没有吃透,明天继续完善关于这个题目的算法解析吧。

好难。。。

本文分享自微信公众号 - TTTEED(TEDxPY),作者:TED

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python 刷题笔记:贪心算法专题三

    今天仍旧是贪心算法的题目,加上之前两篇的四道题,对贪心算法的应用也大致有些印象了,明天换个其它类型题目来继续刷。

    TTTEED
  • Python 版 LeetCode 刷题笔记 #3 无重复字符的最长子串

    今天这题目乍一看,在字符串中找来遍历即可,但实际操作下来,还是有些复杂的,也配得上其中等难度的定位了。

    TTTEED
  • QR 数据编码详解(二)

    每种编码模式针对其字符,不断优化以产生最短的编码二进制串。在此过程中它们采用的编码方法是不同的,本篇将主要解释数据编码过程。

    TTTEED
  • 干货 | iOS 程序员眼中的 Emoji

    ? 一、Emoji 简介 ? ? 绘文字(日语:絵文字/えもじ emoji)是日本在无线通信中所使用的视觉情感符号,绘指图画,文字指的则是字符,可用来代表多种...

    腾讯NEXT学位
  • 人工智能机器人手机

    宇飞来机器人手机是一款全球科技含量最高的手机,它具有以下几点优势: 1 超大内存:用过智能手机的人都知道,如果手机内存太小,你多运行几个软件、多存储一点照片,手...

    企鹅号小编
  • 三分钟了解云手机可以用来做什么?

    云手机使用上和远程电脑类似,在手机或电脑上都可以操作云手机,使用方式和普通手机一样。

    用户7261497
  • 别让生活被手机奴役

    搜狐IT独家 Google Glass横空出世,带来了惊艳的穿戴设备体验,也带来一个全新的感知世界和与人沟通的方式。但科技与生活如何和谐相处的问题前所未有地严峻...

    罗超频道
  • 乔布斯的工业美学输给了手机壳

    下一代IPhone,暂且叫做IPhone6,面世时间未知,各种“谍照”已不断流出:变长,变薄,变轻,窄边框,曲面屏幕,NFC,散热新材料,续航加强,你能...

    罗超频道
  • 你的手机能卖多少钱?快用这款小程序测一下

    如何处理这些闲置或淘汰的设备?也许大多数人都没有特别在意,无形之中其实也是不小的资源浪费和经济损失。

    知晓君
  • JS-字符串截取方法slice、substring、substr的区别

    slice() 方法可通过指定的开始和结束位置,提取字符串的某个部分,并以新的字符串返回被提取的部分。语法如下:

    TimothyJia

扫码关注云+社区

领取腾讯云代金券