首页 > 试题广场 >

最短编辑距离

[编程题]最短编辑距离

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

UNIX系统下有一个行编辑器ed，它每次只对一行文本做删除一个字符、插入一个字符或替换一个字符三种操作。例如某一行的内容是“ABC”，经过把第二个字符替换成“D”、删除第一个字符、末尾插入一个字符“B”，这三步操作后，内容就变成了“DCB”。即“ABC”变成“DCB”需要经过3步操作，我们称它们的编辑距离为3。

现在给你两个任意字符串（不包含空格），请帮忙计算它们的最短编辑距离。

输入描述:

输入包含多组数据。

每组数据包含两个字符串m和n，它们仅包含字母，并且长度不超过1024。

输出描述:

对应每组输入，输出最短编辑距离。

示例1

输入

ABC CBCD
ABC DCB

输出

2
3

算法知识视频讲解

Java

安徒生的谎言

动态规划问题：
import java.io.IOException;
import java.util.Scanner;

public class Levenshtein {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String line = sc.nextLine();
            String s1 = line.split(" ")[0];
            String s2 = line.split(" ")[1];
            int[][] dis = new int[s1.length() + 1][s2.length() + 1];
            for (int i = 0; i <= s1.length(); i++) {
                dis[i][0] = i;
            }
            for (int j = 0; j <= s2.length(); j++) {
                dis[0][j] = j;
            }
            for (int i = 1; i <= s1.length(); i++) {
                for (int j = 1; j <= s2.length(); j++) {
                    dis[i][j] = Math.min(dis[i][j - 1] + 1, Math.min(dis[i - 1][j] + 1,
                            dis[i - 1][j - 1] + (s1.charAt(i - 1) == s2.charAt(j - 1) ? 0 : 1)));
                }
            }
            System.out.println(dis[s1.length()][s2.length()]);
        }

    }
}

发表于 2018-01-26 10:21:25 回复(0)

Java

詆調壹點

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String m = sc.next();
			String n = sc.next();
			int[][] dp = new int[m.length() + 1][n.length() + 1];
			for (int i = 0; i < dp.length; i ++ )
				dp[i][0] = i;
			for (int i = 0; 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 ++ ) {
					dp[i][j] = m.charAt(i - 1) == n.charAt(j - 1) ? dp[i - 1][j - 1] : Math.min(dp[i - 1][j - 1] + 1, Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
				}
			}
			System.out.println(dp[m.length()][n.length()]);
		}
	}
}

发表于 2016-10-12 02:17:22 回复(0)