动态规划-计算字符串距离java

解题思路:
动态规划，dp[][]这里注意一下行列的含义，我们要比对的是str1和str2，所以dp[str1][str2]

当然暴力匹配也是可以的，但不是最优解，还有贪心算法，但也不是最优解

注意事项:

参考代码:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();

      //用一个distances待会存放距离。
       List<Integer> distances = new ArrayList<>();

       //输入n次循环，进到循环里面开始输入每一次的str1和str2，在循环里面调用calculateDistance方法

       //这里calculateDistance务必要返回一个int值，不然到时候打印答案的时候不好处理，把distance放进容器里

       for (int i = 0; i < n; i++) {
           String str1 = sc.next();
           String str2 = sc.next();

           int distance = calculateDistance(str1, str2);
           distances.add(distance);    
       }

       for (int distance : distances) {   //强循环，将distances里面的每个值赋给distance，然后打印出来
           System.out.println(distance);
       }
   }

   public static int calculateDistance(String str1, String str2) {

      //这里初始化数组的时候要注意长度+1
       int[][] dp = new int[str1.length() + 1][str2.length() + 1];
       for (int i = 0; i <= str1.length(); i++) {
           dp[i][0] = i;
       }
       for (int j = 0; j <= str2.length(); j++) {
           dp[0][j] = j;
       }

         //从数组的第二行第二列开始比较   （dp[0][0]=0)

        //如果str1[0]==str2[0] 那么dp[1][1]=dp[0][0]  即=0；

        //如果str1[0]！=str2[0] 那么比较上一次的dp+1的情况和str1与str2哪个数组+1。谁最小

       for (int i = 1; i <= str1.length(); i++) {  

           for (int j = 1; j <= str2.length(); j++) {
               if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                   dp[i][j] = dp[i - 1][j - 1];
               } else {
                   dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j] + 1));
               }
           }
       }

       return dp[str1.length()][str2.length()];
   }
}