wordpress zhaohao网站seo外链

第一题无线基站名字相似度

动态规划

考虑用动态规划解决

char1=input().strip()
char2=input().strip()
n,m=len(char1),len(char2)
dp=[[0]*(m+1) for _ in range(n+1)]
#dp[i][j]定义为以i-1为结尾的char1 和以 j-1为结尾的char2 的最短编辑距离
setA = set('wirel@com')
setB=set('hfv#gbts')
def change_score(a,b):if (a in setA and b in setA) or(a in setB and b in setB):return 1elif (a in setA or a in setB) and (b in setA or b in setB):return 2else:return 3for i in range(n+1):dp[i][0]=i*3
for j in range(m+1):dp[0][j]=j*3for i in range(1,n&