首页 > 试题广场 >

计算字符串的编辑距离

[编程题]计算字符串的编辑距离

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

$\hspace{15pt}$ Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转变成另一个所需的最少单字符编辑操作次数。被允许的转变包括：
$\hspace{23pt}\bullet\,$ 对于任意一个字符串，在任意位置插入一个字符；
$\hspace{23pt}\bullet\,$ 对于任意一个字符串，删除任意一个字符；
$\hspace{23pt}\bullet\,$ 对于任意一个字符串，替换任意一个字符。

$\hspace{15pt}$ 现在，对于给定的字符串 $s$ 和 $t$ ，请计算出它们的编辑距离。

输入描述:

第一行输入一个长度为 ，仅由小写字母组成的字符串 。
第二行输入一个长度为 ，仅由小写字母组成的字符串 。

输出描述:

输出一个整数，表示  和  的编辑距离。

示例1

输入

abcdefg
abcdef

输出

说明

在这个样例中，可以选择将  末尾的  删除。当然，也可以选择在  末尾插入 。

算法知识视频讲解

Python

大溪地渔民

# 思路：dp[i][j] 表示两个字符串分别取到 i, j 位的时候的距离，考虑 a[i] 和 b[j]，有两种情况
# 1、a[i] == b[j]，则 dp[i][j] = dp[i-1][j-1]
# 2、a[i] != b[j]，则 dp[i][j] = min([dp[i-1][j-1], dp[i][j-1], dp[i-1][j]]) + 1


while True:
    try:
        a, b = input(), input()
        dp = []
        for i in range(len(a)+1):
            dp.append([0] * (len(b)+1))
        for i in range(len(a)+1):
            dp[i][0] = i
        for j in range(len(b)+1):
            dp[0][j] = j
        
        for i in range(1, len(a)+1):
            for j in range(1, len(b)+1):
                if a[i-1] == b[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min([dp[i-1][j-1], dp[i][j-1], dp[i-1][j]]) + 1
                    
        print(dp[len(a)][len(b)])
    except:
        break

发表于 2020-12-17 17:25:13 回复(0)

Python

乐天96

#请教各位大佬我想法的错误之处。 #1.对两个字符串进行排序
#2.选择两字符串最小字符的最大值为起点，最大字符的最小值为终点，遍历其中所有字符
#3.如果其中存在二者相等的字符，那么继续向后查找，直到其不再相等，标记其位置
#4.在相等字符前的长度（取二者的最大值）为需要删除/增加之字符
#5.递归查询3中位置之后的字符串


while True:
    try:
        
        def align(s1,s2):
            global cou
            start=max(s1[0],s2[0])#开始字符
            end=min(s1[-1],s2[-1])#结束字符
            
            for i in range(ord(start),ord(end)+1):#i is number
                chri=chr(i)
                if chri in s1 and chri in s2:
                    pos1=s1.index(chri)
                    pos2=s2.index(chri)
                    cou+=max(pos1,pos2)
                    break
            elses1=len(s1)-1
            elses2=len(s2)-1
            while s1[pos1]==s2[pos2] and pos1!=elses1 and pos2!= elses2:
                pos1+=1
                pos2+=1
                
            if pos1==elses1&nbs***bsp;pos2==elses2:
                cou+=max(elses1-pos1,elses2-pos2)
                return 0
            else:
                align(s1[pos1+1:],s2[pos2+1:])

        s1=sorted(input())
        s2=sorted(input())
        cou=0
        align(s1,s2)
        print(cou)
        
    except:
        break

用例:
ixfkieaaocalmxhfifyadnouljtezrnpnfoenespcaenyvzcjtppsaxegmeytqrkvdwugvouskcnnqnmhepquncvyvgkansquaotkgvlvplktrabaikeuubfupunpztpvvzdqaqgfmtzxlcxsipltzwjegpqjzclclvjsmqbmiyzvcujpvhupyhvhhjq
ganxioafstgdpceecubqrngumbpjvwxdpzmragsunvfnmejbcvsoydtbbewybygpsmmyjuvezn

对应输出应该为:

153

你的输出为:

116

我自己思考了下，我忽视了替换字符的作用。但是，这种情况下应该是导致输出变大，为何反而输出变小了呢？

编辑于 2020-06-29 16:26:52 回复(0)

Python

一直爬的蜗牛

def edit_distance(s1,s2):
    len1 = len(s1) + 1
    len2 = len(s2) + 1
    edit = [[i + j for j in range(len2)] for i in range(len1)]
    for i in range(1,len1):
        for j in range(1,len2):
            if s1[i-1] == s2[j-1]:
                d = 0
            else:
                d = 1
            edit[i][j] = min(edit[i][j-1]+1,edit[i-1][j]+1,edit[i-1][j-1]+d)
    return edit[-1][-1]

while True:
    try:
        print(edit_distance(input(), input()))
    except:break

推荐大家看个文章，什么都懂了

https://www.jianshu.com/p/9a53f32cf62b

发表于 2020-05-14 15:39:57 回复(5)

Python

天山剑客

# -*- coding: utf-8 -*-
# !/usr/bin/python3
# 解题思路：动态规划dp[i][j]表示st1[0:j - 1]和st2[0:i - 1]的最小距离；
# 那么st1和st2的距离与dp[i][j], dp[i - 1][j]和dp[i][j - 1]有关；
# 如果st1[j] == st2[i], dp[i + 1][j + 1] = dp[i - 1][j - 1];
# 如果st1[j] != st2[i], dp[i + 1][j + 1] = min(dp[i - 1][j - 1], dp[i - 1][j] + 1, dp[i][j - 1] + 1);
# 边界条件：第0行和第0列表示空字符串分别于st1和st2的子字符串的距离，dp[i][0] = i, dp[0][j] = j


while True:
    try:
        st1 = input()
        st2 = input()

        if len(st1) < len(st2):
            st1, st2 = st2, st1

        m = len(st1)
        n = len(st2)

        res = [[0 for i in range(m + 1)] for i in range(n + 1)]

        for i in range(n + 1):
            res[i][0] = i

        for j in range(m + 1):
            res[0][j] = j

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if st1[j - 1] == st2[i - 1]:
                    res[i][j] = res[i - 1][j - 1]
                else:
                    res[i][j] = min(res[i - 1][j - 1] + 1, res[i - 1][j] + 1, res[i][j - 1] + 1)

        print(res[n][m])

    except:
        break

编辑于 2019-11-20 19:53:55 回复(0)

Python

华201902181743295

'''
生成大小为(N+1)*(M+1)的矩阵dp. dp[x][y]表示A前x个字符串编辑成 B前y个字符所花费的代价.
对于第一行来说,dp[0][y]表示将一个空串变为B的前y个字符组成的子串,花费的代价为ic*y;
同理,对于第一列dp[x][0] = x*dc;

对于其他的位置,dp[x][y]可能有以下几种取值:
    dp[x-1][y-1]+rc;//A[x-1]!=B[y-1] 将前x-1个字符变为B前y-1个字符,再将最后一个字符替换.
    dp[x-1][y-1];//A[x-1]==B[y-1] 将前x-1个字符变为B前y-1个字符,最后一个不用修改.
    dp[x-1][y]+dc;//删除一个字符,将前x-1个字符变为B的前y个字符
    dp[x][y-1]+ic;//将A前x-1个字符变为B的前y个字符,再插入一个字符
    dp[x][y]的值就为以上四者最小的一个.
求解完毕,dp[n][m]即为所求.
--------------------- 
作者：shizheng163 
来源：CSDN 
原文：https://blog.csdn.net/shizheng163/article/details/50988023 
版权声明：本文为博主原创文章，转载请附上博文链接！

'''
while True:
    try:
        #动态规划问题 n*m的矩阵
        datax=input()#竖着放
        datay=input()#横着放
        n=len(datax)+1#要修改的字符串长度
        m=len(datay)+1#修改后的字符串长度
        ic=1#插入操作
        dc=1#删除操作
        rc=1#修改操作
        dp=[]
        for i in range(n):
            dp.append([0]*m)
        for y in range(m):
            dp[0][y]=ic*y
        for x in range(n):
            dp[x][0]=rc*x
        for x in range(1,n):
            for y in range(1,m):
                if datax[x-1]==datay[y-1]:
                    case1=dp[x-1][y-1]
                else:
                    case1=dp[x-1][y-1]+rc
                case2=dp[x-1][y]+dc
                case3=dp[x][y-1]+ic
                dp[x][y]=min(case1,case2,case3)

        print(dp[n-1][m-1])
    except:
        break

发表于 2019-07-12 19:37:16 回复(0)

Python

欧巴禾

while True:
try:
s1=input()
s2=input()
m=len(s1)
n=len(s2)
dp=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(m+1):
if i!=0:
dp[0][i]=i
for j in range(n+1):
if j!=0:
dp[j][0]=j
for i in range(1,n+1):
for j in range(1,m+1):
if s1[j-1]==s2[i-1]:
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1
print(dp[n][m])
except:
break

发表于 2019-05-30 23:02:32 回复(0)

Python

CassielLee

# 经典的动态规划题目，matrix[i][j]代表string1的前i个字符转换到string2前j个字符的
编辑距离,根据第i个字符和第j个字符是否相等就可以得到matrix[i][j]的表达式
def LevenDistance(string1,string2):
    m = len(string2)
    n = len(string1)
    matrix = [[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(1,n+1):
        matrix[i][0] = i 
        for j in range(1, m + 1):
            matrix[0][j] = j
            if string1[i-1] == string2[j-1]:
                matrix[i][j] = min([matrix[i-1][j-1],matrix[i-1][j]+1, matrix[i][j-1]+1])
            else:
                matrix[i][j] = min([matrix[i-1][j-1] , matrix[i-1][j], matrix[i][j-1]]) + 1
    return matrix[n][m]

while True:
    try:
        string1 = input().strip()
        string2 = input().strip()
        print(LevenDistance(string1,string2))
    except:
        break

发表于 2018-08-29 21:04:41 回复(0)

Python

华科平凡

python solution:

def editDistance(str1, str2):
    len1, len2 = len(str1) + 1, len(str2) + 1
    dp = [[0 for i in range(len2)] for j in range(len1)]
    for i in range(len1):
        dp[i][0] = i
    for j in range(len2):
        dp[0][j] = j
    for i in range(1, len1):
        for j in range(1, len2):
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + (str1[i - 1] != str2[j - 1]))
    return dp[-1][-1]


while True:
    try:
        print(editDistance(input(), input()))
    except:
        break

发表于 2017-10-17 14:57:35 回复(11)

Python

龙猫不会说话

借鉴其他人的动态规划

def string_distance(a,b):
    m = len(a) + 1
    n = len(b) + 1
    dp = [[0] * n for i in range(m)] # dp[m][n]
    for i in range(m):
        dp[i][0] = i
    for i in range(n):
        dp[0][i] = i

    for i in range(1,m):
        for j in range(1,n):
            cost = 0 if a[i-1]== b[j-1] else 1
            d1 = dp[i-1][j-1] + cost
            # d2 = dp[i-1][j-1] + 1
            d3 = dp[i-1][j] + 1
            d4 = dp[i][j-1] + 1
            dp[i][j] = min(d1, d3, d4)
    return dp[m-1][n-1]

while True:
    try:
        a = raw_input()
        b = raw_input()
        print string_distance(a,b)
    except:
        break

编辑于 2016-08-23 21:38:54 回复(0)