Python 中最长回文子串问题的解决方法
最长回文子串问题是指在一个字符串中，找出最长的回文子串。回文子串是指正序和倒序读起来都相同的字符串。
解决这个问题的方法有很多，其中一个比较简单的方法是利用动态规划。具体思路如下：
1.定义状态：用一个二维数组dp[i][j]表示从i到j的子串是否是回文串。
2.初始化状态：对于长度为1的子串，dp[i][i]都为True。
3.状态转移：如果一个字符串是回文串，那么它去掉左右两端的字符后仍然是回文串。所以当s[i] == s[j]且dp[i+1][j-1]为True时，dp[i][j]也为True。
4.找到最长回文子串：遍历dp数组，找到长度最长的回文子串。
下面是Python代码演示：
def longestPalindrome(s: str) -> str: n = len(s) dp = [[False] * n for _ in range(n)] ans = "" # 枚举子串的长度 l+1 for l in range(n): # 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置 for i in range(n): j = i + l if j >= n: break if l == 0: dp[i][j] = True elif l == 1: dp[i][j] = (s[i] == s[j]) else: dp[i][j] = (s[i] == s[j] and dp[i + 1][j - 1]) if dp[i][j] and l + 1 > len(ans): ans = s[i:j+1] return ans
测试：
s = "pidancode.com" print(longestPalindrome(s)) # "odanca" s = "皮蛋编程" print(longestPalindrome(s)) # "编"
相关文章