如何比较两个字符串以返回差异数？

Question

我有两条线：

str1：“密码”
str2：“pss$w#rd”

我想比较两个字符串，并想打印输出它们之间的差异总数

输出：

4

由于在str2中删除了“a”、“o”和“$”，因此添加了“#”，因此总运算量为4

但是我的代码给出了错误的输出。我怎样才能解决这个问题？我可能错过了什么

def getMinTotalNumChanges(str1, str2):
    # Write your code here
    totalCount = 0
    
    sorted(str1)
    sorted(str2)
    
    for i in str1:
        for j in str2:
            if i != j:
                totalCount += 1
    return totalCount
    
# driver code
str1 = "password"
str2 = "pss$wr#d"
print(getMinTotalNumChanges(str1, str2))

Answer 1

这是一个非常简单的DP问题，您只需检查删除、编辑和插入：

def getMinTotalNumChanges(str1, str2, memo=None):
    if memo is None:
        memo = {}
    if str1 == "":
        return len(str2)
    if str2 == "":
        return len(str1)
    if (str1, str2) in memo:
        return memo[(str1, str2)]
    diff = 1 if str1[0] != str2[0] else 0
    ret = min(
        # deletion
        1 + getMinTotalNumChanges(str1[1:], str2, memo),
        # edit
        diff + getMinTotalNumChanges(str1[1:], str2[1:], memo),
        # insertion
        1 + getMinTotalNumChanges(str1, str2[1:], memo)
    )
    memo[(str1, str2)] = ret
    return ret


str1 = "password"
str2 = "pss$wr#d"
print(getMinTotalNumChanges(str1, str2))

Answer 2

你可以很容易地一组一组地完成，但它会忽略重复字符的差异和位置差异，比如str1:“password”str2:“ps$w#rd”也会给出结果4。请查看此代码：

def getMinTotalNumChanges(str1, str2):
    str1_set= set(str1)
    str2_set= set(str2)
    str_intersection=str1_set.intersection(str2_set)
    diff1=str1_set - str_intersection
    diff2=str2_set - str_intersection
    total_diff= len(diff1)+len(diff2)
    return total_diff


str1 = "password"
str2 = "pss$wr#d"
print(getMinTotalNumChanges(str1, str2))