字符串算法题目分类与详解

字符串（String） 是算法面试中占比极高的题型，涉及模式匹配、子串/子序列、哈希计数、回文、滑动窗口等多个核心知识点。本文将对字符串常见题型进行系统分类与经典题目解析，帮助你快速掌握解题思路。

---

一、字符串基础操作

1. 反转与变形

🧭 344. 反转字符串

python
def reverseString(s):
    left, right = 0, len(s) - 1
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

🔁 541. 反转字符串 II

python
def reverseStr(s, k):
    s = list(s)
    for i in range(0, len(s), 2 * k):
        s[i:i+k] = reversed(s[i:i+k])
    return ''.join(s)

---

二、字符串匹配与搜索

1. 子串匹配（KMP算法）

🔍 28. 实现 strStr()

• 核心思想：预处理模式串，利用 next 数组避免主串回溯

python
def strStr(haystack, needle):
    if not needle: return 0
    n, m = len(haystack), len(needle)
    # 构建 next 数组
    next_arr = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and needle[i] != needle[j]:
            j = next_arr[j - 1]
        if needle[i] == needle[j]:
            j += 1
            next_arr[i] = j
    # 匹配过程
    j = 0
    for i in range(n):
        while j > 0 and haystack[i] != needle[j]:
            j = next_arr[j - 1]
        if haystack[i] == needle[j]:
            j += 1
        if j == m:
            return i - m + 1
    return -1

2. 通配符匹配

⭐ 44. 通配符匹配

• 动态规划实现：

python
def isMatch(s, p):
    dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]
    dp[0][0] = True
    for j in range(1, len(p) + 1):
        if p[j - 1] == '*':
            dp[0][j] = dp[0][j - 1]
    for i in range(1, len(s) + 1):
        for j in range(1, len(p) + 1):
            if p[j - 1] == '*':
                dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
            elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
    return dp[-1][-1]

---

三、子串与子序列问题

1. 最长公共子序列（LCS）

📊 1143. 最长公共子序列

python
def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

2. 最长回文子串

🌀 5. 最长回文子串

python
def longestPalindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return s[l + 1:r]
    
    res = ""
    for i in range(len(s)):
        odd = expand(i, i)      # 奇数长度
        even = expand(i, i + 1) # 偶数长度
        res = max(res, odd, even, key=len)
    return res

---

四、哈希与计数问题

1. 字母异位词

🧩 242. 有效的字母异位词

python
def isAnagram(s, t):
    return sorted(s) == sorted(t)
    # 或使用 collections.Counter

2. 最小覆盖子串（滑动窗口）

🎯 76. 最小覆盖子串

python
def minWindow(s, t):
    from collections import defaultdict
    need = defaultdict(int)
    for c in t:
        need[c] += 1
    left = 0
    min_len = float('inf')
    start = 0
    missing = len(t)

    for right, c in enumerate(s):
        if need[c] > 0:
            missing -= 1
        need[c] -= 1

        if missing == 0:
            while left < right and need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if right - left + 1 < min_len:
                min_len = right - left + 1
                start = left

    return s[start:start + min_len] if min_len != float('inf') else ""

---

五、字符串编码与解码

1. 字符串压缩

🧱 443. 压缩字符串

python
def compress(chars):
    write = 0
    read = 0
    n = len(chars)
    while read < n:
        current_char = chars[read]
        count = 0
        while read < n and chars[read] == current_char:
            read += 1
            count += 1
        chars[write] = current_char
        write += 1
        if count > 1:
            for c in str(count):
                chars[write] = c
                write += 1
    return write

2. 字符串解码（栈）

🧩 394. 字符串解码

python
def decodeString(s):
    stack = []
    num = 0
    res = ""
    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c == '[':
            stack.append((res, num))
            res, num = "", 0
        elif c == ']':
            prev_str, repeat = stack.pop()
            res = prev_str + res * repeat
        else:
            res += c
    return res

---

六、高频字符串题目列表

类型	经典题目
反转与变形	344. 反转字符串、541. 反转字符串 II
子串匹配	28. 实现 strStr()、44. 通配符匹配
子序列问题	1143. 最长公共子序列、5. 最长回文子串
哈希与计数	242. 字母异位词、76. 最小覆盖子串
编码与解码	443. 压缩字符串、394. 字符串解码

---

七、总结

字符串类题目的核心在于灵活运用多种技巧组合解决问题。

常用技巧包括：

1. ✅ 滑动窗口：如最小覆盖子串
2. 💡 动态规划：如最长公共子序列
3. 🔍 KMP算法：高效子串匹配
4. 🧮 哈希计数：统计字符频率
5. 🔁 中心扩展法：解决回文问题

---

📌 学习建议路径：
字符串反转 → 子串匹配 → 滑动窗口 → 动态规划 → 字符串编码