最长回文子串 python_最长回文子序列

最长回文子串 python_最长回文子序列647.回文子串题目给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。示例1:输入:”abc”输出:3解释:三个回文子串:”a”,”b”,”c”示例2:输入:”aaa”输出:6解释:6个回文子串:”a”,”a”,”a”,”aa”,”aa”,”aaa”提示:输入的字符串长度不会超过10…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

647. 回文子串

题目

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

示例 1:

输入:”abc”

输出:3

解释:三个回文子串: “a”, “b”, “c”

示例 2:

输入:”aaa”

输出:6

解释:6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示:

输入的字符串长度不会超过 1000 。

解题思路

思路:动态规划

先看题目,题目要求在给定的字符串中,求得字符串中有多少个回文子串。其中提及,不同开始或结束位置的子串,即便相同也视为不同子串。

其实看完题目,我们想到最直接的想法就是,先枚举字符的组合,判断这些字符组合成的子串是否是回文串即可。

现在我们来看看,用这种直接的方法代码实现:

class Solution:

def countSubstrings(self, s: str) -> int:

def is_palindrome(string):

“””判断传入字符串是否是回文串

“””

left = 0

right = len(string) – 1

while left < right:

if string[left] != string[right]:

return False

left += 1

right -= 1

return True

# 计数

count = 0

# 枚举字符组合

for i in range(len(s)):

for j in range(i, len(s)):

# 判断字符组合是否是回文串

# 若是计数 +1,否则跳过

sub_string = s[i:j+1]

if is_palindrome(sub_string):

count += 1

return count

上面的方法中,假设字符串长度为 n,我们枚举所有子串需要 $O(n^2)$ 的时间,而判断子串是否回文串需要 $O(S)$ 的时间,S 是子串的长度,所以整个算法的时间是 $O(n^3)$。

这里用 Python 执行结果超时,也侧面说明思路是可行的。这里执行超时的原因如上所述,是因为频繁对字符串切片以及判断子串是否是回文串。

下面我们看看使用动态规划的思路如何解决。

动态规划

假设,s[i…j](i…j 表示这个区间内的字符包含 i、j)是回文串。那么 s[i-1…j+1] 只有在 s[i-1] == s[j+1] 的情况下,才是回文串。

状态定义

现在设 dp[i][j] 表示 s[i…j] 是否是回文串。

状态转移方程

接下来,我们分析一下,子串是回文串成立的情况:

如果 i == j,那么表示是单字符,单字符也是回文串;

如果 s[i] == s[j] 且 i+1=j(或i=j-1),那么这里表示两个字符且相同,那么同样是回文串;

如果 dp[i+1][j-1] == True,也就是 s[i+1…j-1] 是回文串时,若 s[i]==s[j],此时 dp[i][j] 同样也是回文串。

我们可以看到,第二、三种情况是可以合并在一起的。

当 s[i]==s[j],只要 i==j-1 或者 dp[i+1][j-1]==True 其中一个成立,dp[i][j] 都为 True,s[i…j] 是回文串。公式如下:

$dp[i][j] = True, \qquad if , (s[i] == s[j]) , and , (i==j-1 , or , dp[i+1][j-1])$

再看第一种情况,我们发现,其实 i==j 时,s[i] == s[j] 也是成立的,只是此时 i=j-0,。

那么这里再将第一种情况跟上面合并,也就是 i >= j – 1 或者 i – j >= -1 时,公式如下:

$dp[i][j] = True, \qquad if , (s[i] == s[j]) , and , (i-j>=-1 , or , dp[i+1][j-1])$

复杂度分析:

时间复杂度: $O(n^2)$

空间复杂度: $O(n^2)$, dp 数组的开销。

还有 中心扩散法,这个方法能够将空间复杂度降低为常数时间复杂度 $O(1)$。这里在官方题解有给出详细内容,有兴趣的可以从下面链接入口进入了解。

具体的代码实现如下。

代码实现

class Solution:

def countSubstrings(self, s: str) -> int:

# 计数

count = 0

n = len(s)

# 定义 dp 数组,初始化为 False

dp = [[False] * n for _ in range(n)]

# 我们从右往左遍历,填充 dp 数组

for i in range(n-1, -1, -1):

for j in range(i, n):

# 根据文章得出的状态转移方程

if s[i]==s[j] and (i-j>=-1 or dp[i+1][j-1]):

dp[i][j] = True

count += 1

return count

实现结果

最长回文子串 python_最长回文子序列

欢迎关注

公众号 【书所集录】

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/181334.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号