字符串匹配问题
字符串匹配（String Matching）:又称为模式匹配（Pattern Matching）。可以理解为，给定字符串T和P，在主串T中寻找字串P，主串T又被称为文本串，子串p又称为模式串。
在字符串问题中，最重要的问题之一就是字符串匹配问题。而按照模式串的个数，我们可以将字符串匹配问题分为：「单模式串匹配问题」和「多模式串匹配问题」。
344. 反转字符串
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left = 0
right = len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return s
125. 验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
class Solution:
def isPalindrome(self, s: str) -> bool:
left = 0
right = len(s) - 1
while left < right:
# 对于非字母字符直接跳过
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
# 然后判断前后相对应位置上的字符是否相同
if left < right:
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
3. 无重复字符的最长子串
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
- 滑动窗口 + 哈希表
# 使用滑动窗口
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
right = 0
# 字典形式的窗口函数 键：用于统计字符时将同一字符归类；值：表示相同字符的个数
window = dict()
result = 0
while right < len(s):
if s[right] in window:
window[s[right]] += 1
else:
window[s[right]] = 1
# 通过重复的多少，移动窗口
while window[s[right]] > 1:
window[s[left]] -= 1
left += 1
# 更新最大长度
result = max(result, right - left + 1)
# 窗口滑动
right += 1
return result
5. 最长回文子串
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
- 动态规划
# 当子串只有 1 位或 2 位的时候，如果 s[i] == s[j]，该子串为回文子串， dp[i][j] = (s[i] == s[j])。
# 如果子串大于 2 位，则如果 s[i-1: j+1] 是回文串，且 s[i] == s[j]，则 s[i: j] 也是回文串，
# dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]。
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n <= 1:
return s
# 状态转移方程初始化
dp = [[False for _ in range(n)] for _ in range(n)]
max_start = 0 # 记录最长回文子串的起始位置
max_len = 1 # 记录回文字符串的长度
for j in range(1, n):
for i in range(j):
if s[i] == s[j]:
if j - i <= 2:
dp[i][j] = True
else:
dp[i][j] = dp[i + 1][j - 1]
if dp[i][j] and (j - i + 1) > max_len:
max_len = j - i + 1
max_start = i
return s[max_start: max_start + max_len]
49. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
- 哈希表
# 使用哈希表记录字母相同的字符串。
# 对每一个字符串进行排序，按照 排序字符串：字母相同的字符串数组 的键值顺序进行存储。
# 最终将哈希表的值转换为对应数组返回结果。
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
result = []
# 哈希表
hashTable = {}
for s in strs:
# 字符排序
# print(sorted(s)) # 对数组进行排序，按照列表进行输出
s_sort = str(sorted(s))
if s_sort in hashTable:
hashTable[s_sort] += [s]
else:
hashTable[s_sort] = [s]
# 对统计结果进行输出
for index in hashTable:
result.append(hashTable[index])
return result
557. 反转字符串中的单词 III
给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
输入：s = "Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
- 双指针
class Solution:
def reverseWords(self, s: str) -> str:
result = []
s_list = s.split(' ')
print(s_list)
# 对每个字符串进行反转
for s_l in s_list:
s_l = list(s_l)
left = 0
right = len(s_l) - 1
while left < right:
s_l[left], s_l[right] = s_l[right], s_l[left]
left += 1
right -= 1
result.append(''.join(s_l))
return ' '.join(result)
- 切片逆序遍历
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join(word[::-1] for word in s.split(' '))
1. 两数之和
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
# 使用哈希表
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = {}
index = 0
for num in nums:
if target - num in hashtable:
return [hashtable[target-num], index]
hashtable[num] = index
index += 1
15. 三数之和
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
ans = []
for i in range(n):
if i > 0 and nums[i] == nums[i-1]:
continue
left = i + 1
right = n - 1
# 指针移动的条件
while left < right:
while left < right and left > i + 1 and nums[left] == nums[left - 1]:
left += 1
while left < right and right < n - 1 and nums[right] == nums[right + 1]:
right -= 1
if left < right and nums[i] + nums[left] + nums[right] == 0:
ans.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
elif nums[i] + nums[left] + nums[right] < 0:
left += 1
else:
right -= 1
return ans
18. 四数之和
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
# 处理前两位
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len(nums)
nums.sort()
result = []
# i, j 前两位
for i in range(n):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
# left、right 后两位
left = j + 1
right = n - 1
while left < right:
while left < right and left > j + 1 and nums[left] == nums[left - 1]:
left += 1
while left < right and right < n - 1 and nums[right] == nums[right + 1]:
right -= 1
if left < right and nums[i] + nums[j] + nums[left] + nums[right] == target:
result.append([nums[i], nums[j], nums[left], nums[right]])
left += 1
right -= 1
elif nums[i] + nums[j] + nums[left] + nums[right] < target:
left += 1
else:
right -= 1
return result
454. 四数相加 II
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1
# 将O(n4)的时间复杂度转化为O(n2)的时间复杂度
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
nums_dict = {}
for num1 in nums1:
for num2 in nums2:
sum_num = num1 + num2
if sum_num in nums_dict:
nums_dict[sum_num] += 1
else:
nums_dict[sum_num] = 1
count = 0
for num3 in nums3:
for num4 in nums4:
sum_num = num3 + num4
# 求差值
if -sum_num in nums_dict:
count += nums_dict[-sum_num]
return count
