字符串处理模块（5 题）

错题 11：正则表达式匹配（简单版：匹配 “.” 和 “*”）

• 错题题干：实现一个函数，判断字符串 s 是否能被正则表达式 p 匹配，p 中只包含 “.”（匹配任意单个字符）和 “”（匹配前面的字符 0 次或多次）。示例：s="aa"，p="a"→True；s="ab"，p="."→True（.匹配任意字符任意次）；s="aab"，p="cab"→True（c匹配 0 次，a匹配 2 次）。
• 错误代码：

def is_match(s, p):
    i = j = 0
    while i < len(s) and j < len(p):
        if p[j] == '.' or p[j] == s[i]:
            i += 1
            j += 1
        elif p[j] == '*':  # 错误：*必须跟在某个字符后，此处未处理“*与前一个字符的关联”
            # 假设*匹配前面的字符0次，直接跳过*
            j += 1
        else:
            return False
    # 未处理p剩余的*（如s="a"，p="a*"，循环后j=1，需继续处理*）
    return i == len(s) and j == len(p)

• 错误原因分析：1. 未处理 “与前导字符的绑定”：不能单独存在，必须匹配前面的字符（如 p="a" 中匹配 a），原代码将视为独立字符，直接跳过，导致无法匹配多次；2. 未处理 “p 末尾有” 的情况（如 s="a"，p="a*"，循环后 j=1，需判断 j+1 是否为 *，并允许匹配 0 次）。
• 正确代码（递归简化版）：

def is_match(s, p):
    # 边界1：p为空，若s也为空则匹配，否则不匹配
    if not p:
        return not s
    # 边界2：s为空，p需满足“字符+*”循环（如p="a*b*"）
    if not s:
        return len(p) >= 2 and p[1] == '*' and is_match(s, p[2:])
    
    # 核心：判断当前字符是否匹配
    first_match = (p[0] == '.' or p[0] == s[0])
    
    # 若p的第二个字符是*，分两种情况：
    # 1. *匹配0次：跳过p的前两个字符（如p="a*..."→p[2:]）
    # 2. *匹配多次：s向后移1位，p不变（继续匹配s的下一个字符）
    if len(p) >= 2 and p[1] == '*':
        return is_match(s, p[2:]) or (first_match and is_match(s[1:], p))
    # 若p的第二个字符不是*，则当前字符必须匹配，且两者都向后移1位
    else:
        return first_match and is_match(s[1:], p[1:])

• 复盘总结：正则匹配的核心是 “处理的两种选择（匹配 0 次 / 多次）”，递归是简化逻辑的常用方法；需注意的前导字符绑定，避免单独处理 *；可后续优化为动态规划（减少递归重复计算），但递归版更易理解。

错题 12：字符串反转（单词反转，空格保留）

• 错题题干：给定字符串 s（如 "the sky is blue"），反转字符串中的单词顺序，单词内部不反转，且多余空格需删除（如输入 "hello world"→输出 "world hello"）。
• 错误代码：

def reverse_words(s):
    # 错误1：split()默认按任意空格分割，但未处理首尾空格（如"  a b  "→split()→["a","b"]，此处正确，但原代码可能用split(" ")→["","","a","b","",""]，导致错误）
    words = s.split(" ")  # 按单个空格分割，会产生空字符串
    reversed_words = words[::-1]  # 反转单词列表
    return " ".join(reversed_words)  # 错误2：空字符串会导致多余空格（如["","a","b",""]→join后为"  a b  "）

• 错误原因分析：1. 分割方法错误：用s.split(" ")按单个空格分割，会将 “多个空格” 或 “首尾空格” 拆分为空字符串（如 "hello world"→["","","hello","world","",""]）；2. 未过滤空字符串，导致 join 后出现多余空格。
• 正确代码：

def reverse_words(s):
    # 方法1：用split()默认分割（按任意空格，自动过滤首尾空格和多余空格）
    words = s.split()  # 如"  hello world  "→["hello","world"]
    # 方法2：若需手动处理，可先strip()再split(" +")（正则匹配1个及以上空格）
    # import re; words = re.split(r"\s+", s.strip())
    reversed_words = words[::-1]  # 反转单词列表
    return " ".join(reversed_words)  # 用单个空格连接单词

• 复盘总结：Python 字符串分割需区分split()和split(sep)：split()无参数时，按 “任意 whitespace（空格、制表符、换行符）” 分割，且自动过滤首尾空字符串；split(sep)按指定 sep 分割，需手动处理空字符串；处理字符串空格时，优先用split()或正则re.split(r"\s+", s.strip())。

错题 13：回文子串计数（统计所有回文子串）

• 错题题干：给定字符串 s，统计其中所有回文子串的个数（回文子串是连续的，且长度≥1）。示例：s="abc"→3（"a","b","c"）；s="aaa"→6（"a","a","a","aa","aa","aaa"）。
• 错误代码：

def count_substrings(s):
    count = 0
    # 错误：只考虑了长度为1和2的回文，未考虑长度≥3的（如"aaa"中的"aaa"未被统计）
    for i in range(len(s)):
        # 长度为1的回文（单个字符）
        count +=1
        # 长度为2的回文（相邻字符相等）
        if i < len(s)-1 and s[i] == s[i+1]:
            count +=1
    return count

• 错误原因分析：1. 未覆盖 “长度≥3 的回文子串”：回文子串可通过 “中心扩展法” 检测（以单个字符为中心→奇数长度，以两个字符为中心→偶数长度），原代码只检测了中心为 1 个或 2 个字符的基础情况，未向两侧扩展；2. 如 s="aaa"，原代码统计的是 3（长度 1）+2（长度 2：s [0-1]、s [1-2]）=5，遗漏了长度 3 的 "aaa"，导致结果错误。
• 正确代码（中心扩展法）：

def count_substrings(s):
    n = len(s)
    count = 0
    
    def expand(l, r):
        """从l和r为中心扩展，返回回文子串的个数"""
        nonlocal count
        while l >=0 and r < n and s[l] == s[r]:
            count +=1
            l -=1  # 向左扩展
            r +=1  # 向右扩展
    
    # 遍历每个可能的中心
    for i in range(n):
        expand(i, i)    # 奇数长度回文（中心为单个字符i）
        expand(i, i+1)  # 偶数长度回文（中心为i和i+1）
    return count

• 复盘总结：回文子串 / 子序列问题常用 “中心扩展法” 或 “动态规划”，中心扩展法时间复杂度 O (n²)，空间 O (1)，适合字符串长度不大的场景；需明确 “每个中心的两种情况（奇数 / 偶数长度）”，避免遗漏。

错题 14：字符串编码与解码（Base64 简单版）

• 错题题干：实现简单的 Base64 编码（将 ASCII 字符串转换为 Base64 编码），Base64 字符表为 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"，编码规则：3 个字节（24 位）拆分为 4 个 6 位，每个 6 位对应 Base64 字符；若不足 3 个字节，补 0，用 "=" 表示补位次数（如 1 个字节→补 2 个 0→2 个 "="，2 个字节→补 1 个 0→1 个 "="）。示例：s="Man"→编码后 "TWFu"（Man 的 ASCII：77,97,110→二进制 01001101 01100001 01101110→拆分为 010011 010110 000101 101110→对应 Base64 的 T、W、F、u）。
• 错误代码：

base64_chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
def base64_encode(s):
    binary_str = ""
    # 错误1：直接将字符转为二进制，未补前导0至8位（如字符'M'→ASCII77→二进制'1001101'，应补为'01001101'）
    for c in s:
        binary_str += bin(ord(c))[2:]  # bin(77)→'0b1001101'，[2:]后为'1001101'，缺1位前导0
    # 错误2：补0的逻辑错误，未计算补位次数
    while len(binary_str) % 6 != 0:
        binary_str += "0"
    # 错误3：未添加"="补位标识
    encoded = ""
    for i in range(0, len(binary_str), 6):
        chunk = binary_str[i:i+6]
        idx = int(chunk, 2)
        encoded += base64_chars[idx]
    return encoded

• 错误原因分析：1. 二进制字符串补前导 0 错误：每个 ASCII 字符应转为 8 位二进制（不足 8 位补前导 0），原代码直接用bin(ord(c))[2:]，导致位数不足；2. 未记录补位次数（如 1 个字节→补 2 个 0→需加 2 个 "="），编码后无法解码；3. 补 0 逻辑未关联补位次数，仅单纯补 0 至 6 的倍数。
• 正确代码：

base64_chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
def base64_encode(s):
    binary_str = ""
    # 1. 将每个字符转为8位二进制（补前导0）
    for c in s:
        # format(ord(c), '08b')→将ASCII码转为8位二进制字符串（如77→'01001101'）
        binary_str += format(ord(c), '08b')
    # 2. 计算补位次数（不足3个字节时，补0的个数=6 - (len(binary_str) % 6)，补位次数=补0个数//2）
    padding = 0
    while len(binary_str) % 6 != 0:
        binary_str += "0"
        padding += 1
    padding = padding // 2  # 每2个0对应1个"="（因3个字节24位，拆4个6位，缺1个字节→缺8位→需补4个0？不，重新计算：
    # 正确补位次数计算：原字节数n，补位次数 = (3 - n%3) %3（如n=1→补2次，n=2→补1次，n=3→补0次）
    padding = (3 - len(s) % 3) % 3
    # 3. 每6位二进制对应1个Base64字符
    encoded = ""
    for i in range(0, len(binary_str), 6):
        chunk = binary_str[i:i+6]
        idx = int(chunk, 2)
        encoded += base64_chars[idx]
    # 4. 添加补位标识"="
    encoded += "=" * padding
    return encoded

• 复盘总结：字符串编码需严格遵循协议规则（如 Base64 的 8 位转 6 位、补位标识），需注意 “二进制位数的补全” 和 “补位次数的计算”；涉及二进制操作时，优先用format()函数（如format(x, '08b')）确保位数正确，避免手动补 0 出错。

错题 15：字符串子序列判断（判断 s 是否为 t 的子序列）

• 错题题干：给定字符串 s 和 t，判断 s 是否为 t 的子序列（s 的所有字符按顺序出现在 t 中，不要求连续）。示例：s="abc"，t="ahbgdc"→True；s="axc"，t="ahbgdc"→False。
• 错误代码：

def is_subsequence(s, t):
    s_idx = 0
    for char in t:
        if s_idx < len(s) and char == s[s_idx]:
            s_idx += 1
    # 错误：未处理s为空的情况（s为空时，应返回True，原代码s_idx=0，len(s)=0，0==0→True，此处巧合正确，但需明确边界）
    return s_idx == len(s)

• 错误原因分析：1. 边界条件未明确：虽 s 为空时代码返回 True（正确），但未在代码中注释说明，导致后续复盘时可能忽略 “空字符串是任何字符串的子序列” 这一规则；2. 未处理 t 为空的情况（如 s="a"，t=""→应返回 False，原代码 s_idx=0≠1→返回 False，正确，但需明确注释）。
• 正确代码（带边界注释）：

def is_subsequence(s, t):
    """判断s是否为t的子序列（双指针法）"""
    # 边界1：s为空字符串→是任何t的子序列，返回True
    if not s:
        return True
    # 边界2：t为空字符串且s非空→返回False
    if not t:
        return False
    
    s_ptr = 0  # s的指针，指向当前待匹配的字符
    len_s = len(s)
    for char in t:
        if s_ptr < len_s and char == s[s_ptr]:
            s_ptr += 1
            # 优化：若s已完全匹配，提前返回True
            if s_ptr == len_s:
                return True
    # 循环结束后，判断s是否完全匹配
    return s_ptr == len_s

• 复盘总结：子序列判断的核心是 “双指针遍历”，通过 t 的指针逐一匹配 s 的指针；需明确所有边界条件（空字符串），并添加优化（如 s 完全匹配后提前返回），提升代码效率；可扩展为 “多个 s 判断是否为同一 t 的子序列”（如用预处理 t 的字符位置索引，减少重复遍历）。