代码随想录算法训练营Day 56 || 647. 回文子串、516.最长回文子序列

647. 回文子串

力扣题目链接

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

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

示例 1：

• 输入："abc"
• 输出：3
• 解释：三个回文子串: "a", "b", "c"

示例 2：

• 输入："aaa"
• 输出：6
• 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

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

中心扩展法

对于每个可能的“中心点”，向两边扩展，检查以该中心为对称轴的子串是否为回文。

• 这里的“中心点”有两种情况：单个字符（奇数长度的回文子串）和两个相邻字符之间的空隙（偶数长度的回文子串）。
• 对于每个中心，向左和向右同时扩展，比较两边的字符是否相等。
• 每发现一个回文子串，就增加计数。

def countSubstrings(s: str) -> int:
    def expandAroundCenter(left: int, right: int) -> int:
        count = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
        return count

    result = 0
    for i in range(len(s)):
        # 奇数长度的回文子串
        result += expandAroundCenter(i, i)
        # 偶数长度的回文子串
        result += expandAroundCenter(i, i + 1)

    return result

# 测试代码
print(countSubstrings("abc"))  # 应该输出 3
print(countSubstrings("aaa"))  # 应该输出 6

516.最长回文子序列

力扣题目链接(opens new window)

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。

示例 2: 输入:"cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。

提示：

• 1 <= s.length <= 1000
• s 只包含小写英文字母

动态规划

1. 状态定义：创建一个二维数组 dp，其中 dp[i][j] 表示字符串 s 中第 i 到第 j 个字符组成的子串中，最长回文子序列的长度。
2. 状态初始化：对于任何字符串，单个字符都是回文子序列，因此所有 dp[i][i] = 1。
3. 状态转移：
   • 如果 s[i] == s[j]，那么 dp[i][j] = dp[i + 1][j - 1] + 2。
   • 如果 s[i] != s[j]，那么 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。
4. 填充顺序：从字符串末尾开始向前填充 dp 数组，确保每次计算 dp[i][j] 时 dp[i + 1][j] 和 dp[i][j - 1] 已知。

def longestPalindromeSubseq(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]

# 测试代码
print(longestPalindromeSubseq("bbbab"))  # 应该输出 4
print(longestPalindromeSubseq("cbbd"))   # 应该输出 2