第一行输入一个长度为
,仅由小写字母组成的字符串
。
第二行输入一个长度为
,仅由小写字母组成的字符串
。
输出一个整数,表示
和
的编辑距离。
abcdefg abcdef
1
在这个样例中,可以选择将
末尾的
删除。当然,也可以选择在
末尾插入
。
# 思路: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
#请教各位大佬我想法的错误之处。 #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
用例: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
# -*- 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
''' 生成大小为(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
# 经典的动态规划题目,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
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
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