以下是一个使用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链变异程度
- 搜索引擎:提供"您是不是要找…"建议
- 聊天机器人:纠正用户输入错别字