欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 72. 编辑距离

程序员文章站 2022-07-12 08:54:35
...

解决思路:

动态规划

状态数组的含义 dp[i][j]: word1的前i个字符--->word2的前j个字符的最小步数
dp[i][j]=  dp[i-1][j-1]                                         word1[i]==word2[j]
            min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1            word1[i]!=word2[j]

代码:

public static void main(String[] args) {
        String word1 = "horse";
        String word2 = "ros";
        int num = minDistance(word1, word2);
        System.out.println(num);
    }

    /**
     * @Description: 状态数组的含义 dp[i][j]: word1的前i个字符--->word2的前j个字符的最小步数
     *  dp[i][j]=  dp[i-1][j-1]                                         word1[i]==word2[j]
     *             min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1            word1[i]!=word2[j]
     * @Date: 2020/2/6 10:39
     * @Author: fuguowen
     * @Return 
     * @Throws 
     */
    public static int minDistance(String word1, String word2) {
        int i=word1.length();
        int j=word2.length();
        if(i==0){
            return j;
        }
        if(j==0){
            return i;
        }
        //先处理左边界和上边界,然后递推
        int[][] arr=new int[i+1][j+1];
        arr[0][0]=0;
        //不断添加单词
        for(int p=1;p<=j;p++){
            arr[0][p]=arr[0][p-1]+1;
        }
        //不断删除单词
        for(int q=1;q<=i;q++){
            arr[q][0]=arr[q-1][0]+1;
        }

        for(int p=1;p<=i;p++){
            for(int q=1;q<=j;q++){
                if(word1.charAt(p-1)==word2.charAt(q-1)){
                    arr[p][q]=arr[p-1][q-1];
                }else{
                    arr[p][q]=Math.min(Math.min(arr[p-1][q-1],arr[p][q-1]),arr[p-1][q])+1;
                }
            }
        }

        return arr[i][j];
    }

 

相关标签: leetcode