代码随想录刷题第57天|Leetcode647回文子串、Leetcode516最长回文子序列

**代码随想录刷题第57天**

今天我们来解决两个经典的回文问题：LeetCode647 回文子串和 LeetCode516 最长回文子序列。

### LeetCode647 回文子串给定一个字符串 `s`，返回所有可能的回文子串。可以重复选择 `s` 的字符。

**示例1:**

* 输入：`"abcba"`
* 输出：`["abcba", "cab", "bca", "a", "ab", "ac", "bac"]`

**示例2:**

* 输入：`"abcd"`
* 输出：`["a", "b", "c", "d"]`

#### 解决方案我们可以使用回文中心扩展法来解决这个问题。回文中心是指回文子串的中间部分。

class Solution:
 def findSubstrings(self, s: str) -> List[str]:
 n = len(s)
 # 回文中心为单个字符时，回文子串为该字符本身 for i in range(n):
 yield s[i:i+1]
 # 回文中心为两个字符时，回文子串为这两个字符的排列 for i in range(n -1):
 if s[i] == s[i +1]:
 yield s[i:i+2]
 # 回文中心为三个或以上字符时，回文子串为这些字符的排列 for length in range(3, n +1):
 for i in range(n - length +1):
 if s[i] == s[i + length -1]:
 yield s[i:i+length]

class Solution:
 def longestPalindromeSubseq(self, s: str) -> int:
 n = len(s)
 # 动态规划表，dp[i][j]表示s[i:j+1]的最长回文子序列长度 dp = [[0] * (n +1) for _ in range(n +1)]
 # 初始化动态规划表 for i in range(n):
 dp[i][i] =1 # 计算dp[i][j]
 for length in range(2, n +1):
 for i in range(n - length +1):
 j = i + length -1 # 如果s[i:j+1]是回文子串，则直接返回长度 if s[i] == s[j]:
 dp[i][j] = length # 否则，计算dp[i][j]为两种情况的最大值 else:
 dp[i][j] = max(dp[i +1][j], dp[i][j -1])
 return dp[0][n -1]