leetcode 字符串
1143. 最长公共子序列
. - 力扣（LeetCode）
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m=text1.length();int n=text2.length();vector<vector<int>>f(m+1,vector<int>(n+1,0));for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(text1[i-1]==text2[j-1])f[i][j] = f[i-1][j-1]+1;elsef[i][j]= max(f[i-1][j], f[i][j-1]);}}return f[m][n];}
};583. 两个字符串的删除操作
. - 力扣（LeetCode）
方法一：先算出最长公共子序列，在分别（word1.length - f[m][n]）+ (word2.length-f[m][n]);
class Solution {
public:int minDistance(string word1, string word2) {int m=word1.length();int n=word2.length();vector<vector<int>> f(m+1,vector<int>(n+1, 0));for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(word1[i-1]==word2[j-1])f[i][j] = f[i-1][j-1]+1;elsef[i][j] = max(f[i-1][j], f[i][j-1]);}}return m+n-2*f[m][n];}
};方法二：直接定义f[i][j]：word1[0;i]和word2[0:j]变成一样的最小删除次数。
class Solution {
public:int minDistance(string word1, string word2) {int m=word1.length();int n=word2.length();vector<vector<int>> f(m+1,vector<int>(n+1,0));for(int i=0;i<=m;i++)f[i][0] = i;for(int j=0;j<=n;j++)f[0][j] = j;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(word1[i-1]==word2[j-1])f[i][j] = f[i-1][j-1];elsef[i][j] = min(f[i-1][j], f[i][j-1])+1;}} return f[m][n];}
};