字符串编辑距离 public int dynamic(String command,String input) { int dp[][] = new int [command.length()+1][input.length()+1]; dp[0][0]=0; int i,j; for(i=1;i<=command.length();i++) { dp[i][0]=i; } for(j=1;j<=input.length();j++) { dp[0][j]=j; } int f; for(i=1;i<=command.length();i++) { for(j=1;j<=input.length();j++) { if(command.charAt(i-1)==input.charAt(j-1)) f=0; else f=1; dp[i][j]=Math.min(dp[i][j-1]+1, Math.min(dp[i-1][j]+1, dp[i-1][j-1]+ f)); } } return dp[command.length()-1][input.length()-1]; } public String didYouMean(String[] commands, String input) { // write code here int n[] = new int[commands.length]; int min = 65535; int mini=0; for(int i=0;i<commands.length;i++) { n[i]=dynamic(commands[i],input); if(n[i]<min) { min=n[i]; mini=i; } } return commands[mini]; }