Levenshtein Distance (编辑距离——动态规划Java)

package com.patience.interview.huawei;

import java.util.*;

/**
 *
 * Levenshtein Distance
 *
 * @author Green.Gee
 * @date 2022/9/29 13:27
 * @email green.gee.lu@gmail.com
 */
public class LevenshteinDistance {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String l1 = in.nextLine();
        String l2 = in.nextLine();

        int [][] dp = new int[l1.length() + 1][l2.length() + 1];
        for(int i = 1; i < dp.length; i++)
            dp[i][0] = i;

        for(int i = 1; i < dp[0].length; i++)
            dp[0][i] = i;

        for(int i = 1; i < dp.length; i++){
            for(int j = 1; j < dp[0].length; j++){
                if(l1.charAt(i - 1) == l2.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));
                }
            }
        }
        System.out.println(dp[l1.length()][l2.length()]);
    }
}