Java机试题*：【需要动态规划：状态定义状态存储和状态转移】计算字符串的距离(Levenshtein距离/编辑距离)

描述

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家 Levenshtein 提出的，故又叫 Levenshtein Distance 。

Ex：

字符串A: abcdefg

字符串B: abcdef

通过增加或是删掉字符 ”g” 的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。

要求：

import java.util.Scanner;

public class Main {
    public static int optTime = 0;
    /**
     *   初步思路（没有考虑全面）：动态规划，若str1和str2，第一个字符相同，则清除继续递归判断剩下的，若不相同则删除str1第一个字符，并操作加1，用剩下的与str2继续递归。
     *   字符不同的情况，有三种，用一个全局变量无法接收。
     */
     public static void calOptTime(String str1,String str2) {
         // 多或少出来的需要加减操作，多几个加几次
         if(str1.length() == 0) {
             optTime += str2.length();
         // 多或少出来的需要加减操作，多几个加几次
         } else if(str2.length() == 0) {
             optTime += str1.length();
         } else {
             // 相同则，去掉相同继续递归
             if(str1.charAt(0) == str2.charAt(0)) {
                 str1 = str1.substring(1, str1.length());
                 str2 = str2.substring(1, str2.length());
                 calOptTime(str1, str2);
             } else {
                 // 不相同，减、加、或者替换操作，去掉str1的不同，继续递归(此处需要，三种情况下取最小，故：全局变量不能表达，需要状态数组等存储)
                 str1 = str1.substring(1, str1.length());
                 calOptTime(str1, str2);
             }     
         }
     }
     
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = 1;
        String frist = "";
        String second = "";
        while(sc.hasNextLine()){
            if(count % 2 != 0) {
                frist = sc.nextLine();
            } else {
                 // 重置操作次数（距离）
                 optTime = 0;
                 second = sc.nextLine();
                 calOptTime(frist, second);
                 System.out.println(optTime); 
            }
            count++;
        }
    }
}

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            //输入字符串A
            String s1=sc.next();
            //输入字符串B
            String s2=sc.next();
            //计算字符串A和字符串B的距离
            System.out.println(calOptTime(s1,s2));
        }
    }
    private static int calOptTime(String s1,String s2){
        int m=s1.length();
        int n=s2.length();
        //定义dp数组，用于存储记录两个字符串，对应i，j、i-1，j-1...长度下，对应的编辑距离dp[i][j]、dp[i-1][j-1]...
        int[][] dp=new int[m+1][n+1];
        //状态初始化，当一个字符串为空的时候，对应长度位置的编辑距离就是对应的字符串长度
        for(int i=1;i<=m;i++){
            dp[i][0]=i;
        }
        for(int j=1;j<=n;j++){
            dp[0][j]=j;
        }
        //状态转移
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                //如果相等，直接等于前一个位置的情况
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }
                /*
                * 如果不相等，取三种情况（见解题思路）最小的
                */
                else{
                    dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                }
            }
        }
        return dp[m][n];
    }
}

正确思路参考链接：https://blog.nowcoder.net/n/8be215f4ba674af582320e2fc1c52503

总结：

动态规划：可能需要状态定义、状态存储（数组等）和状态转移式、递归、迭代思想、多种情况时，可能还需要用到max、min。