编辑距离总结

判断子序列

可以用双指针快速解决战斗，也可以用动态规划。

问题描述：判断字符串s是否是t的子序列

状态定义：dp[i][j]表示s前i个字符和t前j个字符的匹配长度

状态转移：

• s[i-1]==t[j-1]: dp[i][j] = dp[i-1][j-1] + 1
• 不相等: dp[i][j] = dp[i][j-1](只移动t的指针)

if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = dp[i][j - 1];

不同的子序列

问题描述：要求判断一个字符串在另一个字符串的子序列中的出现次数。

状态定义：dp[i][j]表示s前i个字符中t前j个字符出现的次数

状态转移：

• s[i-1]==t[j-1]: dp[i][j] = dp[i-1][j-1] + dp[i-1][j] (匹配或不匹配)
• 不相等: dp[i][j] = dp[i-1][j] (只能不匹配)

两个字符串的删除操作

问题描述：使两个字符串相同所需的最小删除步数

两种方法：

法一（最长公共子序列法）

状态定义：dp[i][j]表示word1前i个字符和word2前j个字符的最长公共子序列长度

状态转移：

• word1[i-1]==word2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
• 不相等: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

结果：m + n - 2*dp[m][n]

法二（考虑删除操作）

状态定义：dp[i][j]表示word1前i个字符和word2前j个字符相同所需的最小删除步数

状态转移：

• word1[i - 1] == word2[j - 1]: dp[i][j] = dp[i - 1][j - 1];
• word1[i - 1] != word2[j - 1]: dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

编辑距离

问题描述：将一个单词转换成另一个单词所需的最少操作数

状态定义：dp[i][j]表示word1前i个字符转换成word2前j个字符的最少操作数

状态转移：

• word1[i-1]==word2[j-1]: dp[i][j] = dp[i-1][j-1]
• 不相等: dp[i][j] = min(替换,删除,插入) + 1

总结

这几道题可以看作不同约束条件下的字符串编辑问题，编辑距离是通用解法。

逐步从 匹配 --》 选择 -》 删除 -》 替换/插入/删除