python求100到200的回文数,用python编写回文数
47.回文子串
主题
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始或结束位置的子列被视为不同的子列，即使它们由相同的字符组成。
示例1:
输入：abc
输出：3
解释：3个回文子字符串：“A”，“B”，“C”
示例2:
输入：aaa
产出：6
解释：6个回文子串：“A”，“A”，“A”，“aa”，“aa”，“aa”，“aaa”
提示：
的字符串长度不超过1000。
解放思想
理念：动态编程
请先看主题。主语问给定的字符串中有多少个回文子串。这里，不同开始或结束位置的部分列被视为不同的部分列，即使它们是相同的。
其实看完主题，我们想到的最直接的想法就是先列出单词的组合，判断这些单词组成的子串是不是回文串。
现在，让我们用这个直接方法代码来实现它。
类别解决方案：
defcountsubstrings(self，s: str )- int:
Defis _回文(字符串):
" "确定传递的字符串是否是回文字符串。
左=0
Right=len (string)-1
而左右：
If字符串[left]！=string[right]:
返回false
左=1
右-=1
返回true
#计数
计数=0
#枚举字符集
forIinrange(Len ) s):
forjinrange(I，Len ) s)):
确定#字符组合是否是回文字符串。
#计数1，否则跳过。
sub_string=s[i:j 1]
ifis _回文(sub_string):
计数=1
返回计数
在上面的方法中，如果一个字符串的长度为n，则需要$ o (n 2) $来枚举所有子字符串，而需要$o) $ s) $来判断一个子字符串是否返回一个字符串。因为s是子串的长度，所以整个算法的时间是$ o(n ^ 3)$。
这里也从侧面说明Python上的执行结果超时，可以考虑。这个超时的原因是，如上所述，字符串频繁切片或者判断子字符串是否为回文。
我们来看看如何用动态规划的思想来解决。
动态规划
假设s[i.j](i.j表示这个区间的字符包含I和j)是一个回文串。那么，只有当s[i-1]==s[j 1]时，s[i-1.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]都为真，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) $的常数时间复杂度。下面详细介绍一下官方解决问题的方法。感兴趣的朋友请通过以下链接的入口了解。
具体代码实现如下：
代码实现
类别解决方案：
defcountsubstrings(self，s: str )- int:
#计数
计数=0
n=透镜
定义#DP数组并将其初始化为False
DP=[[false]*nfor_inrange(n ) ]
#从右向左遍历以填充dp数组
forIinrange(n-1，-1，-1):
forjinrange(I，n):
#从文章中获得的状态转移方程
ifs[I]==s[j]and(I-j=-1 ordp[i1][j-1]):
DP[I][j]=真
计数=1
返回计数
取得成果
请注意。
微信官方账号【研究所收藏】
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。