编辑距离

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

1 插入一个字符

2 删除一个字符

3 替换一个字符

 

示例 1:

输入: word1 = "horse", word2 = "ros"

输出: 3

解释:

horse -> rorse (将 'h' 替换为 'r')

rorse -> rose (删除 'r')

rose -> ros (删除 'e')

 

示例 2:

输入: word1 = "intention", word2 = "execution"

输出: 5

解释:

intention -> inention (删除 't')

inention -> enention (将 'i' 替换为 'e')

enention -> exention (将 'n' 替换为 'x')

exention -> exection (将 'n' 替换为 'c')

exection -> execution (插入 'u')

 

动态规划

思路

  1. dp[i][j]  word1的前i个字符到word2的前j个字符需要的最少步数。
  2. if  w1[i] =w2[j]  dp[i,j] = dp[i-1,j-1]

        else  dp[i,j] = min(  dp[i-1,j]（减了一个字符）,

                 dp[i,j-1]（增加一个字符）,

                 dp[i-1,j-1]（替换）

                  ) +1

 

public static int minDistance(String word1, String word2) {
          int m = word1.length();
          int n = word2.length();
          int[][] dp = new int[m+1][n+1];
        //dp[i][j]表示word1[0...i]变为word2[0...j]所使用的最少操作数

          for(int i =0;i<=m;i++){
              //初始化:当word1为空字符串“”时，m =0
              dp[i][0] = i;
          }
          for(int j =0;j<=n;j++){
              //初始化:当word2为空字符串“”时.j=0
              dp[0][j] = j;
          }
          for(int i =1;i <= m;i++){
              for(int j =1;j<=n;j++){
                  //末尾字符相同，不需要编辑.(对应字符相等，不操作.)(注意下标，dp[][]下标为从1开始，字符串下标从0开始)
                  if(word1.charAt(i-1) == word2.charAt(j-1)){
                      //所以要减去1
                      dp[i][j] = dp[i-1][j-1];
                  }else {
//                     int max = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] :  dp[i][j-1];
//                     max = (max > dp[i-1][j-1]) ? max :  dp[i-1][j-1];
//                      dp[i][j] = max +1;
                      dp[i][j] = Math.min(dp[i - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1));
                  }
              }
          }
        return dp[m][n];
    }

主函数

public static void main(String[] args) {
        System.out.println("请输入word1与word2");
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine().trim();
        int len = str.length();
        //这里一定要注意，如果没有下一行一定不能再sc.nextLine();
        //int len =sc.nextLine().length();

//        char[] str = new char[len];
//        for(int i =0;i<len;i++){
//            str[i] = sc.nextLine().charAt(i);
//        }
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int[] arr =new int[4];
        int i =0;
        for(int index =0;index <len;index++){
            if('"' == str.charAt(index)){
                stack.push(index);
                arr[i] =index;
                ++i;
            }
        }
             System.out.println(minDistance(str.substring(arr[0]+1,arr[1]),str.substring(arr[2]+1,arr[3])));
    }