【hot100-java】【编辑距离】

多维dp篇

 

 

class Solution {public int minDistance(String word1, String word2) {char [] s=word1.toCharArray();char [] t=word2.toCharArray();int n=s.length;int m=t.length;int [][] f=new int[n+1][m+1];for (int j=1;j<=m;j++){f[0][j]=j;}for(int i=0;i<n;i++){f[i+1][0]=i+1;for(int j=0;j<m;j++){f[i+1][j+1]=s[i]==t[j]?f[i][j]:Math.min(Math.min(f[i][j+1],f[i+1][j]),f[i][j])+1;}}return f[n][m];}
}