🔤 字符串DP — 编辑距离与正则匹配

📖 字符串DP概览

字符串DP的核心是：两个字符串的对齐问题。用二维DP表，行代表一个字符串，列代表另一个字符串，每个格子记录对齐到该位置的某种最优结果。

1. 编辑距离的三种操作

🔬 题目一：编辑距离（LC 72）

给定两个字符串，返回将word1转换成word2所使用的最少操作数。

思路分析

代码实现

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = i  # 全部删除
        for j in range(n + 1):
            dp[0][j] = j  # 全部插入

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]  # 字符匹配
                else:
                    dp[i][j] = 1 + min(
                        dp[i-1][j],     # 删除
                        dp[i][j-1],     # 插入
                        dp[i-1][j-1]    # 替换
                    )
        return dp[m][n]

复杂度分析

时间: O(m * n) 空间: O(m * n)

🔬 题目二：正则表达式匹配（LC 10）

给定字符串s和模式p，实现支持 . 和 * 的正则匹配。

思路分析

代码实现

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for j in range(2, n + 1):
            if p[j-1] == '*':
                dp[0][j] = dp[0][j-2]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j-1] == '*':
                    dp[i][j] = dp[i][j-2] or \
                        (dp[i-1][j] and (p[j-2] == s[i-1] or p[j-2] == '.'))
                else:
                    dp[i][j] = dp[i-1][j-1] and \
                        (p[j-1] == s[i-1] or p[j-1] == '.')
        return dp[m][n]

复杂度分析

时间: O(m * n) 空间: O(m * n)

🔬 题目三：最长回文子串（LC 5）

给定字符串s，返回s中最长回文子串。

思路分析

代码实现

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n <= 1:
            return s
        start, max_len = 0, 1

        def expand(l, r):
            nonlocal start, max_len
            while l >= 0 and r < n and s[l] == s[r]:
                if r - l + 1 > max_len:
                    start = l
                    max_len = r - l + 1
                l -= 1
                r += 1

        for i in range(n):
            expand(i, i)      # 奇数长度回文
            expand(i, i + 1)  # 偶数长度回文
        return s[start:start + max_len]

复杂度分析

时间: O(n^2) 空间: O(1)

面试实战技巧

在实际面试中，算法题不仅仅是写代码，更考察沟通、分析和解决问题的能力。以下是一些实战技巧：

1. 解题步骤模板

2. 常见陷阱

3. 代码模板

# 通用解题模板
class Solution:
    def solve(self, input_data):
        # 1. 边界检查
        if not input_data:
            return default_value
        # 2. 初始化
        result = initial_value
        state = initial_state
        # 3. 主循环
        for item in input_data:
            state = transition(state, item)
            result = max/min/update(result, state)
        # 4. 返回结果
        return result

📝 课后练习

1. LC 44 通配符匹配
2. LC 115 不同的子序列
3. LC 647 回文子串
4. LC 131 分割回文串

🔑 本课要点回顾

• 编辑距离：dp[i][j]=1+min(删,插,改)，匹配时直接继承
• 正则匹配：*的核心=匹配0次(跳过)或匹配1+次(消耗s字符)
• 最长回文子串：中心扩展法O(n^2) O(1)优于DP
• 字符串DP初始化要注意空串情况
• 编辑距离是NLP/生物信息学的基础算法

📚 扩展阅读

• 算法导论 字符串算法章节
• 生物信息学中的序列比对
• LeetCode字符串DP专题

⚡ 进阶专题：常见变体与扩展

每道经典题目都有丰富的变体。掌握核心模板后，灵活应对变体才是面试的真正挑战。以下列举本课相关的高频变体和扩展思路。

1. 常见题目变体

2. 面试中的沟通技巧

# 面试沟通模板
# 1. 先说思路（1-2分钟）
"这道题我想到两种解法，先说更直观的一种..."

# 2. 分析复杂度（30秒）
"时间复杂度O(n^2)，空间可以优化到O(n)"

# 3. 边写边说
"这里我定义dp[i]表示...，转移方程是..."

# 4. 主动验证
"我用示例走一遍：dp[0]=..., dp[1]=..."

# 5. 讨论优化
"空间还可以进一步优化，因为dp[i]只依赖..."

3. 代码调试检查清单