https://leetcode.cn/problems/edit-distance/
class Solution {
public int minDistance(String word1, String word2) {
// 经典题编辑距离
// f[i][j]表示word1前i个字符中选择进行操作,word2前j个字符进行选择进行操作相同的最少步数
// 以word1[i],word2[j]是否相同划分子集
// 相同则不需要考虑word1[i],word2[j],考虑对之前的字符进行操作
// 不同则考虑三个操作,增,删,改,增是加一个字符使得相同,删是删一个字符相同,改是改一个字符使得相同
// 这里有个难点:增和删对于word1和word2都是等价的,目的都是使两个字符串相等,增word1等价删word2,增word2等价删word1
// 因此可以看做只有删word1,删word2,改word1,删word1,则考虑前i-1个元素,删word2则考虑前j-1个元素
// 改一定会相等,因此考虑i-1,j-1个元素
// 有min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1
// f[i][j] = if(word1[i]==word2[j]) f[i-1][j-1]
// else f[i][j]=min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1
// 根据定义有f[1~n][0]=1~n,f[0][1~n]=1~n
int[][] f=new int[510][510];
for(int i=1;i<=word1.length();i++)f[i][0]=i;
for(int i=1;i<=word2.length();i++)f[0][i]=i;
for(int i=1;i<=word1.length();i++)
for(int j=1;j<=word2.length();j++)
{
if(word1.charAt(i-1)==word2.charAt(j-1))f[i][j]=f[i-1][j-1];
else f[i][j]=Math.min(f[i-1][j],Math.min(f[i][j-1],f[i-1][j-1]))+1;
}
return f[word1.length()][word2.length()];
}
}
标签:字符,相同,int,编辑,word1,72,word2,leetcode From: https://www.cnblogs.com/lxl-233/p/18407340