最长回文子串(python3) - 编程思维

问题描述:
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

解决思路:从字符串的第一个字符开始遍历到最后一个字符,判断该字符到第一个字符的子串是否为回文,设立变量更新最长的回文子串长度。

代码如下^-^:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if s == None:
            return None
        length = len(s)
        if length <= 1:
            return s
        dp = [[0 for i in range(length)] for i in range(length)]
        ss = s[0]
        re = 1
        for i in range(0,length):
            for j in range(0,i+1):
                if i-j<=1:
                    if s[j]==s[i]:
                        dp[j][i]=1
                        if re < i-j+1:
                            ss = s[j:i+1]
                            re = i-j+1
                else:
                    if s[j]==s[i] and dp[j+1][i-1]:
                        dp[j][i]=1
                        if re < i-j+1:
                            ss = s[j:i+1]
                            re = i-j+1
        return ss

时间与空间复杂度:

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl...

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://segmentfault.com/a/1190000020737624

电话号码的字母组合(python3) - 编程思维

题目描述:给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。给出数字到字母的映射如下(与电话按键相同)。注意1不对应任何字母。示例:输入:"23"输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]说明:尽管上面的答案是按字典序排列的,但是你

全排列(python3) - 编程思维

题目描述:给定一个没有重复数字的序列,返回其所有可能的全排列。 示例:输入: [1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 解题思路: 代码如下: class Solution: def permute(self, nums: List[

组合总和(python3) - 编程思维

题目描述:给定一个无重复元素的数组 candidates 和一个目标数 target ,找出candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。说明:所有数字(包括 target)都是正整数。解集不能包含重复的组合。  示例 1:输入: candidat

两数相加(python3) - 编程思维

提出问题:给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储一位数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外,这两个数都不会以 0 开头。示例:输入:(2 -> 4 -> 3) + (5

如何实现字符串加字符串 - 编程思维

之前我们讲到了数字类型可以使用+加号来计算,其实+加号不仅可以用来计算,还可以用于字符串的连接。 字符串加字符串 我们来看一下字符串是如何加字符串: 从上图我们可以看出,两个字符串相加,输出结果就是将两个字符串按顺序连接起来。在前面的字符串输出时也在前面位置,如果字符串本身没有空格,那么输出时字符串之间也是没有空格的

linux之ack命令 - 编程思维

ack是比grep好用的文本搜索工具ack命令安装> yum install -y ack命令特点默认搜索当前工作目录默认递归搜索子目录忽略元数据目录,比如.svn,.git,CSV等目录忽略二进制文件(比如pdf,image,coredumps)和备份文件(比如foo~,*.swp)在搜索结果中打印行号,有助于

es6:模板字符串 - 编程思维

前言传统的字符串模板在传统的Javascript中,如果我们对DOM进行操作,字符串模板通常采用加号( + )进行字符串拼接。ES6模板字符串反引号( ` )表示普通的字符串,也可以表示多行字符串(随意换行),同时还可以插入变量(代替传统的加号拼接)。简介模板字符串使用反引号 (``) 来代替普通字符串中的用双引号和单

es6新特性4:字符串的扩展 - 编程思维

一、ES5字符串函数  concat: 将两个或多个字符的文本组合起来,返回一个新的字符串  indexOf: 返回字符串中一个子串第一处出现的索引(从左到右搜索)。如果没有匹配项,返回 -1   charAt: 返回指定位置的字符  lastIndexOf: 返回字符串中一个子串最后一处出现的索引(从右到左搜索),如