583. 两个字符串的删除操作
题目
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例：
输入: “sea”, “eat” 输出: 2 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
思路
转化成最长公共子序列问题就可以了
代码
public int minDistance(String word1
, String word2
) {
int n
= word1
.length();
int m
= word2
.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(word1
.charAt(i
-1)==word2
.charAt(j
-1)){
f
[i
][j
] = Math
.max(f
[i
][j
],f
[i
-1][j
-1]+1);
}
}
}
return n
+m
-2*f
[n
][m
];
}
