首页 > 试题广场 >

最短编辑距离

[编程题]最短编辑距离

热度指数：2023 时间限制：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

算法知识视频讲解

Python

张澳

python可以过呀

def shortestDistance(s1, s2):
    l1, l2 = len(s1) + 1, len(s2) + 1
    a, b = '0' + s1, '0' + s2
    dp = [[0] * l2 for i in range(l1)]
    for i in range(1, l1): dp[i][0] = i
    for i in range(1, l2): dp[0][i] = i
    '''
    a[i]添加之后相同，需要a[1~i]=b[1~j-1],dp[i][j]=dp[i][j-1]+1
    a[i]删除之后相同，需要a[1~i-1]=b[1~j],dp[i][j]=dp[i-1][j]+1
    a[i]修改之后相同，需要a[1~i-1]=b[1^j-1],dp[i][j]=dp[i-1][j-1]+1
    也可能a[i]不需要修改，就能a[1~i]=b[1~j],dp[i][j]=dp[i-1][j-1]
    '''
    for i in range(1, l1):
        for j in range(1, l2):
            dp[i][j] = min(dp[i][j - 1] + 1, dp[i - 1][j] + 1,
                           dp[i - 1][j - 1] + int(a[i] != b[j]))
    return dp[l1 - 1][l2 - 1]

import sys
x = sys.stdin.read()[:-1]
xx = x.split("<br/>")
ans = ""
for i in xx:
    s1, s2 = i.split()
    ans += f"{shortestDistance(s1, s2)}<br/>"
sys.stdout.write(ans[:-5])

发表于 2021-01-28 14:09:29 回复(0)

Python

京酱玫瑰

#Q2：levenshtein distance:
            n =int(input('input n strings:'))
            list = []
            edit_distance = 0
            for i in range(n):
                #print('input string %d:'%(i+1))
                list.append( input('input string %d:'%(i+1)))
            target = input('the target string is:')
            for string1 in list:
                num = 1
                print(string1)
                print(target)
                if string1 != '' and target != '':
                    m = len(string1) #the horizontal axis
                    n = len(target) #the vertical axis
                    #initialize:
                    d_matrix  = np.mat(np.zeros((n+1,m+1)))
                    for i in range(m):
                        d_matrix[0,i+1] = i+1
                    for i in range(n):
                        d_matrix[i+1,0] = i+1
                    #print(d_matrix)
                    f = 1
                    j = 1
                    for cha_j in target:
                        i = 1
                        #print(d_matrix[1,5])
                        for cha_i in string1:
                            if cha_i == cha_j:
                                f = 0
                            else:
                                f = 1
                            d_matrix[j,i]=min(d_matrix[j,i-1]+1,d_matrix[j-1,i]+1,d_matrix[j-1,i-1]+f)
                            i += 1
                        j +=1
                    edit_distance = d_matrix[n,m]
                else:
                    if string1 =='' and target =='':
                        edit_distance = 0
                    elif string1 =='':
                        edit_distance = len(target)
                    else:
                        edit_distance = len(string)
                print("the edit distance of string %d: "%(num),edit_distance)

编辑于 2018-07-11 20:16:54 回复(0)

Python

华科平凡

python通不过这道题目，希望能解决一下。

还是把代码贴一下：

def minDistance(word1, word2):
    l1, l2 = len(word1) + 1, len(word2) + 1
    dp = [[0 for i in range(l2)] for j in range(l1)]
    for i in range(l1):
        dp[i][0] = i
    for j in range(l2):
        dp[0][j] = j
    for i in range(1, l1):
        for j in range(1, l2):
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (word1[i - 1] != word2[j - 1]))
    return dp[-1][-1]


while True:
    try:
        word1,word2=input().split()
        print(minDistance(word1,word2))
    except:
        break

发表于 2017-11-15 22:10:31 回复(2)