数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python 中的最长回文子串
假设我们有一个字符串 S。我们需要找到 S 中的最长回文子串。我们假设字符串 S 的长度为 1000。所以如果字符串是“BABAC”，那么最长回文子串是“BAB”。
为了解决这个问题，我们将遵循以下步骤
- 定义一个与字符串长度相同的方阵，并用 False 填充它
- 将主对角线元素设置为 True，因此 DP[i, i] = True，对于所有从 0 到 order – 1 的 i
- start := 0
- for l in range 2 to length of S + 1
- for i in range 0 to length of S – l + 1
- end := i + l
- 如果 l = 2，则
- 如果 S[i] = S[end - 1]，则
- DP[i, end - 1] = True，max_len := l，并且 start := i
- 如果 S[i] = S[end - 1]，则
- 否则
- 如果 S[i] = S[end - 1] 并且 DP[i + 1, end - 2]，则
- DP[i, end - 1] = True，max_len := l，并且 start := i
- 如果 S[i] = S[end - 1] 并且 DP[i + 1, end - 2]，则
- for i in range 0 to length of S – l + 1
- 返回从索引 start 到 start + max_len 的子字符串
示例（Python）
让我们看看以下实现以获得更好的理解 -
class Solution(object):
def longestPalindrome(self, s):
dp = [[False for i in range(len(s))] for i in range(len(s))]
for i in range(len(s)):
dp[i][i] = True
max_length = 1
start = 0
for l in range(2,len(s)+1):
for i in range(len(s)-l+1):
end = i+l
if l==2:
if s[i] == s[end-1]:
dp[i][end-1]=True
max_length = l
start = i
else:
if s[i] == s[end-1] and dp[i+1][end-2]:
dp[i][end-1]=True
max_length = l
start = i
return s[start:start+max_length]
ob1 = Solution()
print(ob1.longestPalindrome("ABBABBC"))输入
"ABBABBC"
输出
"BBABB"
更新于: 2020年4月27日
10K+ 浏览量
广告