动态规划在字符串匹配中的艺术：从编辑距离到正则匹配

探索动态规划如何优雅地解决复杂的字符串匹配问题，从基础编辑操作到强大的模式匹配引擎

字符串处理是计算机科学的核心问题之一，而动态规划为字符串匹配提供了系统性的解决方案框架。本文将深入探讨几种经典的字符串匹配问题及其动态规划解法，并使用C++实现完整解决方案。

1. 字符串匹配问题的动态规划视角

动态规划解决字符串匹配问题的核心思想是：将复杂匹配问题分解为子问题，利用重叠子问题性质避免重复计算，并通过最优子结构找到最优解。

1.1 动态规划在字符串问题中的优势

• 系统化：提供统一的解题框架

• 高效性：时间复杂度通常为O(n²)或O(nm)

• 灵活性：可处理各种约束条件

• 可解释性：递推关系清晰反映问题本质

2. 编辑距离：字符串相似度度量

编辑距离（Levenshtein距离）衡量两个字符串的相似程度，定义为将一个字符串转换为另一个字符串所需的最少操作次数，允许的操作包括插入、删除、替换。

2.1 问题定义

给定两个字符串word1和word2，计算它们的最小编辑距离。

示例：输入: word1 = "horse", word2 = "ros"
输出: 3
解释:
horse -> rorse (将'h'替换为'r')
rorse -> rose (删除第二个'r')
rose -> ros (删除'e')

2.2 动态规划解法

状态定义

定义dp[i][j]表示word1的前i个字符转换为word2的前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-1]
dp[i][j-1], // 在word1中插入word2[j-1]
dp[i-1][j-1] // 替换word1[i-1]为word2[j-1]
);
}

完整实现

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class EditDistance {
public:
int minDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();

// 创建DP表
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

// 初始化边界条件
for (int i = 0; i <= m; i++) {
dp[i][0] = i; // 将word1的前i个字符变为空串
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j; // 将空串变为word2的前j个字符
}

// 状态转移
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], // 删除
dp[i][j-1], // 插入
dp[i-1][j-1] // 替换
});
}
}
}

return dp[m][n];
}

// 空间优化版本
int minDistanceOptimized(string word1, string word2) {
int m = word1.length();
int n = word2.length();

// 确保word1是较短的字符串，以优化空间
if (m < n) {
swap(word1, word2);
swap(m, n);
}

vector<int> prev(n + 1, 0);
vector<int> curr(n + 1, 0);

// 初始化第一行
for (int j = 0; j <= n; j++) {
prev[j] = j;
}

for (int i = 1; i <= m; i++) {
curr[0] = i; // 对应dp[i][0]
for (int j = 1; j <= n; j++) {
if (word1[i-1] == word2[j-1]) {
curr[j] = prev[j-1];
} else {
curr[j] = 1 + min({
prev[j], // 删除
curr[j-1], // 插入
prev[j-1] // 替换
});
}
}
prev = curr;
}

return prev[n];
}
};

int main() {
EditDistance ed;

vector<pair<string, string>> testCases = {
{"horse", "ros"},
{"intention", "execution"},
{"", "abc"},
{"abc", ""},
{"abc", "abc"}
};

cout << "编辑距离测试：" << endl;
for (auto& test : testCases) {
int result1 = ed.minDistance(test.first, test.second);
int result2 = ed.minDistanceOptimized(test.first, test.second);
cout << "minDistance(\"" << test.first << "\", \"" << test.second
<< "\") = " << result1
<< " (优化版本: " << result2 << ")" << endl;
}

return 0;
}