删除单词之间的距离

Question

我试图找到需要删除多少个字符才能使两个单词相同.例如"at","cat"将为1,因为我可以删除c,"boat"和"got"将是3,因为我可以删除b,a和g以使其成为ot.我将这些单词放入字典中,将其计数作为值.然后我迭代字典并查看该键是否存在于另一个字典中,否则我将差值加1.这是一个非常低效的算法吗？

但它高估了我需要的删除次数.

def deletiondistance(firstword, secondword):
dfw = {}
dsw = {}
diff = 0
for i in range(len(firstword)):
    print firstword[i]
    if firstword[i] in dfw:
        dfw[firstword[i]]+=1
    else:
        dfw[firstword[i]]=1
for j in range(len(secondword)):
    if secondword[j] in dsw:
        dsw[secondword[j]] +=1
    else:
        dsw[secondword[j]]=1

for key, value in dfw.iteritems():

    if key in dsw:
        #print "key exists"
        pass

    else:
        diff +=1

print "diff",diff

Answer 1

正如 @Hulk 提到的，这类似于 levenshtein 距离。唯一的区别是不允许替换，但可以通过使用替换成本 2 来纠正，这与从两个字符串中删除字符相同。例子：

def dist(s1, s2):
    cur = list(range(len(s2) + 1))
    prev = [0] * (len(s2) + 1)
    for i in range(len(s1)):
        cur, prev = prev, cur
        cur[0] = i + 1
        for j in range(len(s2)):
            # Substitution is same as two deletions
            sub = 0 if s1[i] == s2[j] else 2
            cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1)

    return cur[-1]

cases=[('cat','bat'),
       ('bat','cat'),
       ('broom', 'ballroom'),
       ('boat','got'),
       ('foo', 'bar'),
       ('foobar', '')]

for s1, s2 in cases:
    print('{} & {} = {}'.format(s1, s2, dist(s1, s2)))

输出：

cat & bat = 2
bat & cat = 2
broom & ballroom = 3
boat & got = 3
foo & bar = 6
foobar &  = 6