企业官网建设流程全解析

备赛锚点：第十八届蓝桥杯软件赛报名季已开启（2026-10-08—12-18，省赛 2027-04-10，C/C++·Python 程序设计 9:00–13:00），其官方考点清单明确把「动态规划」与「字符串处理」列为省赛高频方向；全国青少年信息素养大赛算法应用赛项、电子学会 Python/C++ 考级也都将「字符串距离 / 相似度」作为经典上岸题。今天这篇，就拆解其中最常被考到、却又最容易写错的——编辑距离（Edit Distance，又称莱文斯坦距离 Levenshtein Distance）。

一、题目目标：校园古诗文默写校对

【原创题】校园古诗文默写校对系统

语文老师让学生默写古诗，但手打录入时常见三种笔误：

• 打错字（把"尽"打成"近"）→ 需要一次替换；
• 漏打字（多打了字）→ 需要一次删除；
• 多打字（少打了字）→ 需要一次插入。

给定标准答案串S和学生录入串T，求：最少需要多少次单字符编辑操作（插入 / 删除 / 替换），才能把T变成S？

这正是经典算法"编辑距离"要解决的问题。

举几个校园化的例子帮大家建立直觉：

注意：编辑距离不允许"交换相邻两字符算一次"。如果题目真有"相邻交换算 1 次"，那是另一类变体（如"最小邻换次数"），不能直接套本模板——这点后面易错点会再强调。

二、核心考点（为什么它是高频题）

编辑距离是线性动态规划 + 字符串的交叉考点，几乎是算法入门的分水岭题：

1. 状态设计：如何用二维dp表达"两个前缀之间的关系"——这是所有"双串"类 DP（LCS、最长公共子串、字符串交错等）的共同范式。
2. 边界处理：空串到任意串的距离，对应"全删 / 全插"。
3. 三选一转移：插入、删除、替换三种操作取最小，漏掉任意一种都会 WA。
4. 空间优化：滚动数组把O(nm)降到O(min(n,m))，是考级与省赛写题的加分项。
5. 路径还原：不仅求"最小步数"，还能输出"具体怎么改"，对应真实的拼写纠错、代码查重需求。

在蓝桥杯省赛中，编辑距离常以"字符串变换最少步数""DNA 相似度""单词纠错"等面孔出现；在电子学会 Python/C++ 考级里，它属于"二维动态规划"章节的必练题。

三、解法拆解：Wagner–Fischer 动态规划

3.1 状态定义

设dp[i][j]= 把S的前i个字符（S[0..i-1]）变成T的前j个字符（T[0..j-1]）所需的最少操作数。

3.2 边界条件

• dp[0][j] = j：空串变T的前j个字符，只能连续插入j次。
• dp[i][0] = i：S的前i个字符变空串，只能连续删除i次。

3.3 状态转移

考察S[i-1]与T[j-1]（注意是i-1/j-1，字符串下标比 dp 维少 1）：

• 若S[i-1] == T[j-1]：这一位本来就一样，无需操作，dp[i][j] = dp[i-1][j-1]。
• 若不同：从下面三种操作里取最小，再加 1 次本次操作：
• 删除S[i-1]：dp[i-1][j]
• 插入T[j-1]：dp[i][j-1]
• 替换S[i-1] → T[j-1]：dp[i-1][j-1]

综上：

dp[i][j] = dp[i-1][j-1] (S[i-1]==T[j-1]) dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) (否则)

3.4 C++ 实现

#include <bits/stdc++.h> using namespace std; // 完整二维 DP 版 int editDistance(const string& s, const string& t) { int n = s.size(), m = t.size(); vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); for (int i = 0; i <= n; i++) dp[i][0] = i; // 删光 s for (int j = 0; j <= m; j++) dp[0][j] = j; // 插满 t for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (s[i - 1] == t[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[n][m]; } // 滚动数组版，空间 O(min(n, m)) int editDistanceRoll(const string& s, const string& t) { string a = s, b = t; if (a.size() < b.size()) swap(a, b); // 让列数 = 短串长度 int n = a.size(), m = b.size(); vector<int> pre(m + 1); for (int j = 0; j <= m; j++) pre[j] = j; for (int i = 1; i <= n; i++) { vector<int> cur(m + 1); cur[0] = i; for (int j = 1; j <= m; j++) { if (a[i - 1] == b[j - 1]) cur[j] = pre[j - 1]; else cur[j] = 1 + min({pre[j], cur[j - 1], pre[j - 1]}); } pre = move(cur); } return pre[m]; } int main() { string s = "horse", t = "ros"; cout << editDistance(s, t) << "\n"; // 3 cout << editDistanceRoll(s, t) << "\n"; // 3 return 0; }

3.5 Python 实现

def edit_distance(s: str, t: str) -> int: n, m = len(s), len(t) # dp[i][j] = 把 s 的前 i 个字符变成 t 的前 j 个字符的最少操作数 dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(n + 1): dp[i][0] = i # s 前 i 个删光 for j in range(m + 1): dp[0][j] = j # 插入 t 的前 j 个 for i in range(1, n + 1): for j in range(1, m + 1): if s[i - 1] == t[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = 1 + min(dp[i - 1][j], # 删除 s[i-1] dp[i][j - 1], # 插入 t[j-1] dp[i - 1][j - 1]) # 替换 return dp[n][m] # 滚动数组版，空间 O(min(n, m)) def edit_distance_roll(s: str, t: str) -> int: if len(s) < len(t): s, t = t, s # 让 t 为短串，按列滚动 n, m = len(s), len(t) pre = list(range(m + 1)) # dp[0][j] for i in range(1, n + 1): cur = [i] + [0] * m for j in range(1, m + 1): if s[i - 1] == t[j - 1]: cur[j] = pre[j - 1] else: cur[j] = 1 + min(pre[j], cur[j - 1], pre[j - 1]) pre = cur return pre[m] if __name__ == "__main__": print(edit_distance("horse", "ros")) # 3 print(edit_distance_roll("horse", "ros")) # 3 print(edit_distance("白日依山尽", "白日依山近")) # 1

3.6 进阶：不仅求步数，还能输出"怎么改"

在 DP 表上记录每个格子是从哪个前驱来的，再逆推即可还原编辑路径——这正是拼写纠错软件"标红告诉你哪改错了"的原理。

def edit_distance_path(s: str, t: str): n, m = len(s), len(t) dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(n + 1): dp[i][0] = i for j in range(m + 1): dp[0][j] = j for i in range(1, n + 1): for j in range(1, m + 1): if s[i - 1] == t[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]) # 回溯 ops, i, j = [], n, m while i > 0 or j > 0: if i > 0 and j > 0 and s[i - 1] == t[j - 1]: ops.append(("保持", s[i - 1])); i -= 1; j -= 1 elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1: ops.append(("替换", t[j - 1], s[i - 1])); i -= 1; j -= 1 elif i > 0 and dp[i][j] == dp[i - 1][j] + 1: ops.append(("删除", s[i - 1])); i -= 1 else: ops.append(("插入", t[j - 1])); j -= 1 ops.reverse() return dp[n][m], ops # 示例：edit_distance_path("horse", "ros") 返回最小距离 3 以及一条具体编辑路径

四、时间 / 空间复杂度

其中n、m是两串长度。务必用int足够：最大距离不超过max(n, m)，对常规赛题int绰绰有余；若题目明示"答案对大质数取模"（罕见），再按需取模。C++ 中用int即可，不要无谓开long long拖慢常数；但若与别的数值运算混用，注意统一类型避免溢出。

五、七个易错点（省赛 / 考级高频踩坑）

1. 边界写漏：只初始化了dp[i][0]忘了dp[0][j]，或反过来，导致空串对拍时结果错误。两个方向的边界必须都初始化。
2. 下标错位：转移里写成s[i]、t[j]，应该是s[i-1]、t[j-1]。DP 维比字符串下标多 1，这是双串 DP 最经典的 off-by-one。
3. 三选一取最小，漏操作：只比较了"替换"，忘了"插入dp[i][j-1]"或"删除dp[i-1][j]"，结果偏小或偏大。三者缺一不可。
4. 相同字符也 +1：S[i-1] == T[j-1]时直接继承dp[i-1][j-1]，不要 +1；有人图省事统一 +1，距离会整个偏大。
5. 滚动数组方向搞反：按列滚动时，pre数组必须保留"上一行"完整值，cur[j]依赖pre[j]（上一行同列）、cur[j-1]（本行已算）、pre[j-1]（左上）。若用二维则无此忧，但空间更大。
6. 空串 / 长度 0 未特判：虽然 DP 边界已覆盖，但若你在外面提前return或访问s[0]，可能越界。稳妥起见让 DP 自己处理空串。
7. 把"相邻交换"当成 1 次：标准莱文斯坦距离里，交换相邻两字符 = 删除 + 插入 =2 次，不是 1 次。若题目说"交换算 1 次"，那是 Damerau–Levenshtein 变体，需额外处理相邻转置，不能套本模板。

六、进阶玩法（冲国赛 / 信息素养复赛）

• 路径还原：如上 3.6，记录操作矩阵回溯，输出具体编辑步骤，用于"相似度 + 差异展示"。
• 与 LCS 的关系：若只允许"插入 / 删除"两种操作（不允许替换），则编辑距离 =n + m - 2·LCS(S, T)。这是把"公共子序列"和"编辑距离"两题打通的关键等式。
• 带权编辑：不同字符替换代价不同（如键盘相邻键误触代价小），把1 +改成对应权重即可，转移结构不变。
• 拼写纠错 Top-K：在词典里对所有词求编辑距离，取最小的前 K 个返回候选——搜索引擎"你是不是要找"的核心逻辑。
• 对角带优化：当限定编辑距离 ≤k时，只需计算主对角线两侧宽度为2k+1的带状区域，复杂度降到O(k·min(n,m))，处理长文本查重必备。
• 近似串匹配：在长文本中找出"与模式串编辑距离 ≤ k 的所有位置"，用于敏感词识别、论文查重。

七、小结与互动

编辑距离是"双串线性 DP"的范式题：状态 = 两前缀、转移 = 三操作取最小、边界 = 全删/全插。吃透它，LCS、最长公共子串、字符串交错、最短超序列等一串双串 DP 都会顺着同一套路被你拿下——这正好是蓝桥杯省赛、全国青少年信息素养大赛算法赛项、电子学会 Python/C++ 考级共同的高频得分点。

今日互动：
- 你在练习时，遇到过"要求相邻交换只算 1 次"的变体题吗？欢迎在评论区贴出题目，我们一起用 Damerau–Levenshtein 思路拆解。
- 想看哪类双串 DP 的实战拆解？留言告诉我，下一篇接着聊。

觉得有用就点个赞 / 收藏，备赛路上一起进阶 🚀

📚 免费少儿编程资料（夸克网盘领取）

以下资料来自夸克网盘分享，点击链接可直接保存；若需在 App 内打开，也可复制下方明文链接：

1. 全国青少年信息素养大赛复赛集训题目Python&C++.docx
   https://pan.quark.cn/s/93995d3cb150
2. 2024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdf
   https://pan.quark.cn/s/da97b5dbf75d
3. Python背记手册.pdf
   https://pan.quark.cn/s/7568ae9ca92b
4. Python课程
   https://pan.quark.cn/s/a94bf02d00c6
5. 2024信息素养大赛图形化复赛集训题答案3-9
   https://pan.quark.cn/s/6ccab7ec3cbc
6. 2025年03月份电子学会考级真题
   https://pan.quark.cn/s/4403c4228912
7. 2025全国青少年信息素养大赛赛项说明
   https://pan.quark.cn/s/d9d0df4a9f29
8. 青少儿信息素养大赛编程资料
   https://pan.quark.cn/s/4ab6bd83be8a

资料持续更新，关注获取最新分享。