数据结构与算法之 LeetCode 字符串题：回文串与最长公共子串技巧解析
在 LeetCode 上，字符串题目是算法挑战中的一大类，其中回文串和最长公共子串是两个非常经典的题目。这两个问题不仅考察了我们对字符串操作的理解，还涉及了动态规划、双指针等算法技巧。本文将围绕这两个主题，深入探讨其解题思路和代码实现。
一、回文串
回文串是指正读和反读都相同的字符串。例如，“abba”和“racecar”都是回文串。
1.1 解题思路
判断一个字符串是否为回文串，最直观的方法是将字符串反转，然后比较反转后的字符串与原字符串是否相同。这种方法的时间复杂度为 O(n^2)，其中 n 是字符串的长度。
更高效的方法是使用双指针技术。我们定义两个指针，一个指向字符串的开头，另一个指向字符串的结尾。然后，我们逐个比较这两个指针所指向的字符，如果它们相同，则将两个指针都向中间移动一位，继续比较。如果遇到不相同的字符，则说明该字符串不是回文串。
1.2 代码实现
python
def is_palindrome(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
1.3 优化
对于空字符串和只包含一个字符的字符串，它们都是回文串。我们可以对上述代码进行优化，减少不必要的比较。
python
def is_palindrome(s: str) -> bool:
if len(s) < 2:
return True
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
二、最长公共子串
最长公共子串是指两个字符串中都存在的最长连续子串。例如，字符串“ABABC”和“BABCAC”的最长公共子串是“BABC”。
2.1 解题思路
解决最长公共子串问题，我们可以使用动态规划。定义一个二维数组 dp，其中 dp[i][j] 表示以 s1[i-1] 和 s2[j-1] 结尾的最长公共子串的长度。
状态转移方程为：如果 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = 0。
2.2 代码实现
python
def longest_common_substring(s1: str, s2: str) -> str:
m, n = len(s1), len(s2)
dp = [[0] (n + 1) for _ in range(m + 1)]
max_len = 0
end_pos = 0
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > max_len:
max_len = dp[i][j]
end_pos = i
else:
dp[i][j] = 0
return s1[end_pos - max_len:end_pos]
2.3 优化
上述代码的时间复杂度为 O(mn)，其中 m 和 n 分别是两个字符串的长度。我们可以通过空间优化来降低空间复杂度。
python
def longest_common_substring(s1: str, s2: str) -> str:
m, n = len(s1), len(s2)
dp = [0] (n + 1)
max_len = 0
end_pos = 0
for i in range(1, m + 1):
prev = 0
for j in range(1, n + 1):
temp = dp[j]
if s1[i - 1] == s2[j - 1]:
dp[j] = prev + 1
if dp[j] > max_len:
max_len = dp[j]
end_pos = i
else:
dp[j] = 0
prev = temp
return s1[end_pos - max_len:end_pos]
三、总结
本文介绍了 LeetCode 上两个经典的字符串题目：回文串和最长公共子串。通过分析解题思路和代码实现，我们了解了双指针技术和动态规划在解决字符串问题中的应用。在实际编程中，熟练掌握这些技巧将有助于我们解决更多类似的算法问题。
Comments NOTHING