题目描述:Leetcode 0072 编辑距离
分析
-
本题的考点:动态规划。
-
用a表示word1,用b表示word2,分析如下:
代码
- C++
class Solution { public: int minDistance(string a, string b) { int n = a.size(), m = b.size(); a = ' ' + a, b = ' ' + b; vector> f(n + 1, vector (m + 1)); // 初始化 for (int j = 0; j <= m; j++) f[0][j] = j; // 将空字符串变为b[1~j]需要j步添加操作 for (int i = 0; i <= n; i++) f[i][0] = i; // 将a[1~i]变为空字符串需要i步删除操作 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1); if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]); else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1); } return f[n][m]; } };
- Java
class Solution { public int minDistance(String word1, String word2) { int n = word1.length(), m = word2.length(); char[] a = (" " + word1).toCharArray(), b = (" " + word2).toCharArray(); int[][] f = new int[n + 1][m + 1]; for (int i = 0; i <= m; i++) f[0][i] = i; for (int i = 0; i <= n; i++) f[i][0] = i; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { f[i][j] = Math.min(f[i - 1][j], f[i][j - 1]) + 1; if (a[i] == b[j]) f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]); else f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1); } return f[n][m]; } }
- Python
class Solution: def minDistance(self, a: str, b: str) -> int: n = len(a); m = len(b) a = " " + a; b = " " + b f = [[0 for _ in range(m + 1)] for _ in range(n + 1)] for j in range(m + 1): f[0][j] = j for i in range(n + 1): f[i][0] = i for i in range(1, n + 1): for j in range(1, m + 1): f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1) if a[i] == b[j]: f[i][j] = min(f[i][j], f[i - 1][j - 1]) else: f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1) return f[n][m]
时空复杂度分析
-
时间复杂度: O ( n × m ) O(n times m) O(n×m),n、m为两个字符串的长度。
-
空间复杂度: O ( n × m ) O(n times m) O(n×m)。
题目描述:Leetcode 0583 两个字符串的删除 *** 作
分析
-
本题的考点:动态规划。
-
本题是Leetcode 0072 编辑距离的简化版,可以转化为LC 0072的做法。
-
题目中的 *** 作是删除两个字符串的任意字符,删除word2中的字符相当于在word1中添加字符,因此对word1的 *** 作可以是删除和添加。对于word1中的某个字符进行修改的话可以等价于首先删除word1中的某个字符,然后在删除的位置添加一个字符,因此修改 *** 作步数是两步。
-
这样,问题就变成了我们对word1进行增(1步)、删(1步)、改(2步) *** 作,最少多少步可以变为word2。分析和LC 0072一样,如下:
-
和LC 0072的唯一区别在于,改的公式中加的是2。
-
最后值得一提的是,本题还可以转化为求最长公共子序列。当我们求出两个序列的最长公共子序列的长度后,假设为len,则最终的答案为word1.size() + word2.size() - len * 2。
代码
- C++
// LC 0072的做法 class Solution { public: int minDistance(string a, string b) { int n = a.size(), m = b.size(); a = ' ' + a, b = ' ' + b; vector> f(n + 1, vector (m + 1)); // 初始化 for (int j = 0; j <= m; j++) f[0][j] = j; // 将空字符串变为b[1~j]需要j步添加操作 for (int i = 0; i <= n; i++) f[i][0] = i; // 将a[1~i]变为空字符串需要i步删除操作 for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1); if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]); else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 2); // 也可以没有这句话,因为已经被f[i-1][j]包含 } return f[n][m]; } };
- Java
// LCS的做法 class Solution { public int minDistance(String a, String b) { char[] as = a.toCharArray(), bs = b.toCharArray(); int n = a.length(), m = b.length(); int[][] f = new int[n + 1][m + 1]; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]); if (as[i - 1] == bs[j - 1]) f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1); } return n + m - f[n][m] * 2; } }
- Python
# LC 0072的做法 class Solution: def minDistance(self, a: str, b: str) -> int: n, m = len(a), len(b) f = [[0 for _ in range(m + 1)] for _ in range(n + 1)] for i in range(n + 1): f[i][0] = i for i in range(m + 1): f[0][i] = i for i in range(1, n + 1): for j in range(1, m + 1): f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1 if a[i - 1] == b[j - 1]: f[i][j] = min(f[i][j], f[i - 1][j - 1]) return f[n][m]
时空复杂度分析
-
时间复杂度: O ( n × m ) O(n times m) O(n×m),n、m为两个数组长度。
-
空间复杂度: O ( n × m ) O(n times m) O(n×m)。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)