字符串回文子串（中心扩展法）在LeetCode中的应用
在编程领域，字符串回文子串是一个经典的问题。回文串是指正读和反读都相同的字符串，例如“abba”和“madam”。在LeetCode等编程竞赛平台上，字符串回文子串问题经常以不同的形式出现，其中中心扩展法是一种解决该问题的有效算法。本文将围绕中心扩展法，探讨如何在LeetCode上解决字符串回文子串问题。
中心扩展法简介
中心扩展法是一种寻找字符串中所有回文子串的方法。其基本思想是，对于字符串中的每一个字符（或字符对），将其视为可能的回文中心，然后向两侧扩展，直到不再满足回文条件为止。
中心扩展法的步骤
1. 初始化：定义一个函数，接收字符串作为输入。
2. 遍历字符串：对于字符串中的每一个字符（或字符对），将其视为中心。
3. 向两侧扩展：从中心向两侧扩展，检查两侧的字符是否相同。
4. 记录回文子串：如果两侧的字符相同，则记录下这个回文子串。
5. 重复步骤2-4，直到遍历完所有可能的中心。
中心扩展法的代码实现
python
def expandAroundCenter(s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]
def findPalindromeSubstrings(s):
result = set()
for i in range(len(s)):
奇数长度的回文子串
palindrome_odd = expandAroundCenter(s, i, i)
result.add(palindrome_odd)
偶数长度的回文子串
palindrome_even = expandAroundCenter(s, i, i + 1)
result.add(palindrome_even)
return list(result)
示例
s = "babad"
print(findPalindromeSubstrings(s))
LeetCode上的字符串回文子串问题
在LeetCode上，字符串回文子串问题有多种变体，以下是一些常见的题目：
1. 最长回文子串（LeetCode 5）
2. 回文子串数量（LeetCode 647）
3. 回文子串的最大长度（LeetCode 516）
最长回文子串（LeetCode 5）
题目描述：给定一个字符串`s`，找到`s`中任意位置的最长回文子串。
python
def longestPalindrome(s):
if not s:
return ""
start, end = 0, 0
for i in range(len(s)):
len1 = expandAroundCenter(s, i, i)
len2 = expandAroundCenter(s, i, i + 1)
max_len = max(len1, len2)
if max_len > end - start:
start = i - (max_len - 1) // 2
end = i + max_len // 2
return s[start:end + 1]
示例
s = "babad"
print(longestPalindrome(s))
回文子串数量（LeetCode 647）
题目描述：给定一个字符串`s`，返回`s`中回文子串的数量。
python
def countSubstrings(s):
return len(findPalindromeSubstrings(s))
示例
s = "babad"
print(countSubstrings(s))
回文子串的最大长度（LeetCode 516）
题目描述：给定一个字符串`s`，返回`s`中回文子串的最大长度。
python
def longestPalindromeSubseq(s):
n = len(s)
dp = [[0] n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for cl in range(2, n + 1):
for i in range(n - cl + 1):
j = i + cl - 1
if s[i] == s[j] and cl == 2:
dp[i][j] = 2
elif s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
return dp[0][n - 1]
示例
s = "bbbab"
print(longestPalindromeSubseq(s))
总结
中心扩展法是一种简单而有效的解决字符串回文子串问题的算法。在LeetCode上，通过运用中心扩展法，我们可以解决多种与回文子串相关的问题。本文介绍了中心扩展法的基本原理和代码实现，并展示了如何在LeetCode上应用这一方法解决实际问题。希望本文能帮助读者更好地理解和掌握字符串回文子串问题的解决方法。
Comments NOTHING