最长公共子序列编辑距离

最长公共子序列

解题思路

子序列本质上就是选或不选，考虑最后一对字母，分别为 \(x\) 和 \(y\)，那么根据选或不选，将会出现以下四种情况，分别是：

1. 不选 \(x\) 不选 \(y\)
2. 不选 \(x\) 选 \(y\)
3. 选 \(x\) 不选 \(y\)
4. 选 \(x\) 选 \(y\)

回溯三问：

1. 当前操作？
   考虑 \(s[i]\) 和 \(s[j]\) 选或不选
2. 子问题？
   \(s\) 的 前 \(i\) 个字母和 \(t\) 的前 \(j\) 个字母的 \(LCS\) 长度
3. 下一个子问题？
   \(s\) 的前 \(i\) 个字母和 \(t\) 的前 \(j-1\) 个字母的 \(LCS\) 长度
   \(s\) 的前 \(i-1\) 个字母和 \(t\) 的前 \(j\) 个字母的 \(LCS\) 长度
   \(s\) 的前 \(i-1\) 个字母和 \(t\) 的前 \(j-1\) 个字母的 \(LCS\) 长度

于是，可以得到：

\[dfs(i, j)=\begin{cases}max(dfs(i-1,j),dfs(i,j-1),dfs(i-1,j-1)+1), s[i]=t[j] \\max(dfs(i-1,j),dfs(i,j-1)), s[i] \neq t[j] \end{cases}\]

考虑两个问题：

1. 当 \(s[i]=t[j]\) 时，我们需要考虑只选其中一个的情况吗？
   不考虑，因为 \(dfs(i-1, j-1) + 1 \geq dfs(i-1,j)\)， \(dfs(i-1,j-1) + 1 \geq dfs(i-1, j-1)\)
2. 当 \(s[i]\neq t[j]\) 时，我们需要考虑都不选的情况吗？
   不用考虑，因为 \(dfs(i-1,j) \geq dfs(i-1,j-1)\)，\(dfs(i,j-1) \geq dfs(i-1,j-1)\)

代码实现

1. 记忆化搜索

点击查看代码

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.size();// 记忆化搜索vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1));auto dfs = [&](this auto&& dfs, int i, int j) -> int {if (i < 0 || j < 0) {return 0;}auto& res = dp[i][j];if (res != -1) {return res;}if (text1[i] == text2[j]) {res = max({dfs(i-1,j),dfs(i,j-1),dfs(i-1,j-1)+1});} else {res = max(dfs(i-1, j), dfs(i,j-1));}return res;};return dfs(m - 1, n - 1);}
};

• 时间复杂度：\(O(m*n)\)
• 空间复杂度：\(O(m*n)\)

2. 递推
   已知

\[dfs(i,j)=\begin{cases} dfs(i-1,j-1)+1, & s[i]=t[j] \\ max(dfs(i-1,j), dfs(i,j-1)), & s[i]\neq t[j] \end{cases}\]

可以进一步得到：

\[f[i][j]=\begin{cases} f[i-1][j-1]+1,&s[i]=t[j] \\ max(f[i-1][j],f[i][j-1]), &s[i] \neq t[j]\end{cases}\]

\[f[i+1][j+1]=\begin{cases} f[i][j]+1,&s[i]=t[i] \\ max(f[i][j+1],f[i+1][j]),&s[i] \neq t[j]\end{cases}\]

点击查看代码

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.size();// 记忆化搜索vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (text1[i] == text2[j]) {f[i+1][j+1] = f[i][j] + 1;} else {f[i+1][j+1] = max(f[i][j+1], f[i+1][j]);}    }};return f[m][n];  }
};

• 时间复杂度：\(O(m*n)\)
• 空间复杂度：\(O(m*n)\)

3. 优化空间复杂度，两个一维数组

点击查看代码

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.size();vector<vector<int>> f(2, vector<int>(n + 1, 0));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (text1[i] == text2[j]) {f[(i+1)%2][j+1] = f[i%2][j] + 1;} else {f[(i+1)%2][j+1] = max(f[i%2][j+1], f[(i+1)%2][j]);}    }};return (m & 1) == 0 ? f[0][n]: f[1][n];  }
};

\(m\) 若是偶数，最后一位一定不为 \(0\)。换句话说，若 \(m\) 是偶数，则 \((m \& 1) == 0\)。

• 时间复杂度：\(O(m*n)\)
• 空间复杂度：\(O(n)\)

4. 优化空间复杂度，用一个数组

用一个数组更新时，涉及到到底是顺序遍历还是逆序遍历的问题。例如这一道题，当前的状态依赖于同一行左边的元素，所以就一定是顺序遍历更新。

点击查看代码

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.size();vector<int> f(n + 1, 0);for (int i = 0; i < m; ++i) {int prev = 0;for (int j = 0; j < n; ++j) {int temp = f[j + 1];if (text1[i] == text2[j]) {f[j+1] = prev + 1;} else {f[j+1] = max(f[j+1], f[j]);}  prev = temp;}};return f[n];}
};

• 时间复杂度：\(O(m*n)\)
• 空间复杂度：\(O(n)\)

编辑距离

解题思路

编辑距离：等价转换

\[s=horse \]

\[t=ros \]

删除一个字母，相当于去掉 \(s[i]\)；
插入一个字母，相当于给 \(s[i]\) 的位置 插入 \(t[j]\rightarrow\) 可以理解为，去掉 \(t[j]\)；
替换一个字母，就好像把 \(s\) 单词末尾的 \(e\) 给替换成 \(s\)，从而使 \(s[i]\) 和 \(s[j]\) 都去掉。
如果 \(s[i]=t[j]\)，那就都去掉。
如果不等于，
综上，可以得到

\[dfs(i,j)=\begin{cases}dfs(i-1,j-1), s[i]=t[j], \\min(\underset{\substack{\uparrow \\ \text{插入}}}{dfs(i, j - 1)}, \underset{\substack{\uparrow \\ \text{删除}}}{dfs(i - 1, j)},\underset{\substack{\uparrow \\ \text{替换}}}{dfs(i-1,j-1)})+1, s[i]\neq t[j] \end{cases}\]

问题1：在相等的情况下，需要考虑 \(dfs(i-1,j)\) 和 \(dfs(i,j-1)\) 吗？
不需要

代码实现

1. 记忆化搜索

点击查看代码

class Solution {
public:int minDistance(string word1, string word2) {// 记忆化搜索int m = word1.size(), n = word2.size();vector<vector<int>> dp(m, vector<int>(n, -1));auto dfs = [&](this auto&&dfs, int i, int j) -> int {if (i < 0) {return j + 1;}if (j < 0) {return i + 1;}auto& res = dp[i][j];if (word1[i] == word2[j]) {res = dfs(i - 1, j - 1);} else {res = min({dfs(i, j - 1), dfs(i - 1, j), dfs(i - 1, j - 1)}) + 1;}return res;};return dfs(m - 1, n - 1);}
};

• 时间复杂度：\(O(m*n)\)
• 空间复杂度：\(O(m*n)\)

2. 翻译成递推的形式
   已知

\[dfs(i,j)=\begin{cases}dfs(i-1,j-1), s[i]=t[j], \\min(\underset{\substack{\uparrow \\ \text{插入}}}{dfs(i, j - 1)}, \underset{\substack{\uparrow \\ \text{删除}}}{dfs(i - 1, j)},\underset{\substack{\uparrow \\ \text{替换}}}{dfs(i-1,j-1)})+1, s[i]\neq t[j] \end{cases}\]

那么

\[f[i][j]=\begin{cases}f[i-1][j-1], s[i]=t[j], \\min(f[i][j - 1], f[i - 1][j], f[i-1][j-1])+1, s[i]\neq t[j] \end{cases}\]

进一步得到

\[f[i+1][j+1]=\begin{cases}f[i][j], s[i]=t[j], \\min(f[i+1][j], f[i][j+1], f[i][j])+1, s[i]\neq t[j] \end{cases}\]

点击查看代码

class Solution {
public:int minDistance(string word1, string word2) {// 递推int m = word1.size(), n = word2.size();// 初始化vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));for (int j = 0; j < n; ++j) {f[0][j] = j;}for (int i = 0; i < m; ++i) {f[i+1][0] = i+1;for (int j = 0; j < n; ++j) {if (word1[i] == word2[j]) {f[i+1][j+1] = f[i][j];} else {f[i+1][j+1] = min({f[i+1][j], f[i][j+1], f[i][j]}) + 1;}}}return f[m][n];}
};

• 时间复杂度：\(O(m*n)\)
• 空间复杂度：\(O(m*n)\)

3. 优化成2个数组

点击查看代码

class Solution {
public:int minDistance(string word1, string word2) {// 递推int m = word1.size(), n = word2.size();// 初始化vector<vector<int>> f(2, vector<int>(n + 1, 0));for (int j = 0; j <= n; ++j) {f[0][j] = j;}for (int i = 0; i < m; ++i) {f[(i+1)%2][0] = i+1;for (int j = 0; j < n; ++j) {if (word1[i] == word2[j]) {f[(i+1)%2][j+1] = f[i%2][j];} else {f[(i+1)%2][j+1] = min({f[(i+1)%2][j], f[i%2][j+1], f[i%2][j]}) + 1;}}}return (m & 1) == 0 ? f[0][n]: f[1][n];}
};

• 时间复杂度：\(O(m*n)\)
• 空间复杂度：\(O(n)\)

4. 优化成一维数组

点击查看代码

class Solution {
public:int minDistance(string word1, string word2) {// 递推int m = word1.size(), n = word2.size();// 初始化vector<int> f(n + 1, 0);for (int j = 0; j <= n; ++j) {f[j] = j;}for (int i = 0; i < m; ++i) {int prev = f[0];f[0] = i+1;for (int j = 0; j < n; ++j) {int temp = f[j + 1];if (word1[i] == word2[j]) {f[j+1] = prev;} else {f[j+1] = min({f[j], f[j+1], prev}) + 1;}prev = temp;}}return f[n];}
};

• 时间复杂度：\(O(m*n)\)
• 空间复杂度：\(O(n)\)