字符串最小变换次数

[编程题]字符串最小变换次数

热度指数：3134 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定两个字符串，已知可以使用三种方式进行变换
1. 插入一个字符
2. 删除一个字符
3. 更改一个字符

请设计一个算法，找到两个字符串之间的经历几次最小变换，可以字符串1转换成字符串2

数据范围：输入字符串的长度满足 $1 \le n \le 1000 \$

输入描述:

输入两个字符串

输出描述:

最小变换次数

示例1

输入

hello
helle

输出

算法知识视频讲解

Java

何止hz

编辑距离问题

1.递归解法，理解起来非常简单

import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-05-09 21:17
 * @Description:
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        int ans = recursion(s1, s2, s1.length(), s2.length());
        System.out.println(ans);
    }
    private static int recursion(String s1, String s2, int i, int j) {
        //由s1 --> s2
        if (j == 0) {
            return i;
        } else if (i == 0) {
            return j;
        } else if (s1.charAt(i-1) == s2.charAt(j - 1)) {//跳过
            return recursion(s1, s2, i - 1, j - 1);
        } else {
            int m1 = recursion(s1, s2, i - 1, j) + 1;//删掉一个字符
            int m2 = recursion(s1, s2, i, j - 1) + 1;//增加一个字符
            int m3 = recursion(s1, s2, i - 1, j - 1) + 1;//替换一个字符
            return Math.min(Math.min(m1, m2), m3);
        }
    }
}

2.动态规划解法

import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-05-09 21:17
 * @Description:
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        int ans = dynamicPlanning(s1, s2);
        System.out.println(ans);
    }
    private static int dynamicPlanning(String s1, String s2){
        int len1 = s1.length();
        int len2 = s2.length();
        int dp[][] = new int[len1+1][len2+1];
        for (int j = 1; j <= len2; j++)
            dp[0][j] = j;
        for (int i = 1; i <= len1; i++)
            dp[i][0] = i;
        for (int i = 1; i <= len1; i++)
            for (int j = 1; j <= len2; 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[len1][len2];
    }
}

编辑于 2020-05-10 09:14:30 回复(0)

Java

Mr.X-Ray

import java.util.Scanner;
public class AtoB {
    //一个字符串变成另一个字符串，允许的每次操作是增加/修改/删除一个字符，求最少的操作次数
    //我的思路是：研究出了一种规律，在最长公共子串的基础上，长的那个的不同字符数就是答案
    //如果是长度相同的两个字符串,如果最后一个相同的字符的位置在第一个不同的之后就要+1，如：
    //hello helle ,4 < 5 不用+1
    //helol hello ,5 < 4 +1
    static int last_com=-1;
    static int first_dif=-1;
    public static int common(String a,String b) {
        //动态规划最长公共子串
        //状态转换方程，等于则在左上角+1，意思是两个字符串同时扩大符合；否则就在两个字符串单个扩大下找最大
        int alen=a.length();
        int blen=b.length();
        int[][] dp=new int[alen+1][blen+1];
        for(int i=1;i<=alen;i++) {
            for(int j=1;j<=blen;j++) {
                if(a.charAt(i-1)==b.charAt(j-1)) {
                    dp[i][j]=dp[i-1][j-1]+1;//表的下标和字符串的不一样
                    last_com=i;//记录最后一个相同的下标
                }
                else {
                    if(i==j&&first_dif==-1) first_dif=i;
                    dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[alen][blen];
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            String a = sc.nextLine();
            String b = sc.nextLine();
            int res = common(a,b);
            res = Math.max(a.length(), b.length())-res;//不相同的字符数，在长的那一个字符
            if(a.length()!=b.length()) System.out.println(res);
            else {
                if(last_com>first_dif)//判断是否最后不同在最开始相同之后
                    System.out.println(res+1);
                else System.out.println(res);
            }
        }
        sc.close();
    }
}

发表于 2019-09-10 09:25:11 回复(0)