以下是一个使用C++实现的编辑距离算法（Levenshtein Distance）示例，通过动态规划计算两个字符串之间的最小编辑操作次数（插入、删除、替换）：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int minEditDistance(const string& word1, const string& word2) {int m = word1.length(), n = word2.length();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));// 初始化边界条件for (int i = 0; i <= m; ++i) dp[i][0] = i; // 删除所有字符for (int j = 0; j <= n; ++j) dp[0][j] = j; // 插入所有字符// 填充DP表for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {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], // 删除word1[i]dp[i][j-1], // 插入word2[j]dp[i-1][j-1] // 替换字符});}}}return dp[m][n];
}int main() {string word1 = "kitten"; // 示例输入1string word2 = "sitting"; // 示例输入2int distance = minEditDistance(word1, word2);cout << "从 \"" << word1 << "\" 到 \"" << word2 << "\" 的最小编辑距离为: " << distance << endl;// 解释：kitten → sitten（替换k为s）→ sittin（替换e为i）→ sitting（插入g）return 0;
}
算法核心思想演示（文本修正场景）
想象场景：将单词"kitten"修正为"sitting"，计算最少需要多少次单字符编辑操作：
| 操作步骤 | 结果变化 | 操作类型 |
|---|---|---|
| 1. 替换首字母k | kitten → sitten | 替换（1次） |
| 2. 替换中间e | sitten → sittin | 替换（2次） |
| 3. 插入尾字母g | sittin → sitting | 插入（3次） |
动态规划三步走
-
定义状态表
dp[i][j]表示将word1[0..i-1]转换为word2[0..j-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], # 删除word1字符dp[i][j-1], # 插入word2字符dp[i-1][j-1] # 替换字符) -
填表示例（kitten vs sitting）
“” s i t t i n g “” 0 1 2 3 4 5 6 7 k 1 1 2 3 4 5 6 7 i 2 2 1 2 3 4 5 6 t 3 3 2 1 2 3 4 5 t 4 4 3 2 1 2 3 4 e 5 5 4 3 2 2 3 4 n 6 6 5 4 3 3 2 3
执行结果
从 "kitten" 到 "sitting" 的最小编辑距离为: 3
算法特性
| 特性 | 说明 |
|---|---|
| 时间复杂度 | O(m*n) （m,n为字符串长度） |
| 空间复杂度 | O(m*n) （可优化为O(n)） |
| 优势 | 精准量化文本相似度 |
| 适用场景 | 拼写检查、生物信息学、语音识别 |
关键代码解析
-
边界初始化
dp[i][0] = i; // 删除i次得到空串 dp[0][j] = j; // 插入j次得到目标串 -
递推逻辑优化
使用min({a,b,c})同时比较三种操作，保证代码简洁 -
空间压缩技巧
使用滚动数组可将空间复杂度降至O(n)（示例未展示）
实际应用场景
- 文档比对工具：自动计算文稿修改量
- 基因序列分析：比对DNA链变异程度
- 搜索引擎：提供"您是不是要找…"建议
- 聊天机器人：纠正用户输入错别字
)
