Levenshtein distance

概念

莱文斯坦距离Levenshtein distance)是将一个单词更改为另一个单词所需的最少编辑操作次数。莱文斯坦距离允许的编辑操作包括单个字符的 替换/插入/删除。

实例

给定字符串kittensitting,前者可以通过以下步骤变换成后者:

  1. kitten → sitten (将k替换为s)

  2. sitten → sittin (将e替换为i)

  3. sittin → sitting (在尾部插入g)

无法通过更少的步骤完成替换,故两者的莱文斯坦距离为3

算法

请输入图片描述

实现

def levenshteinDistance(s1, s2):
    m = len(s1)
    n = len(s2)
    dt = []

    # 初始化距离表
    for i in range(m+1):
        temp = []
        for j in range(n+1):
            if i==0:
                temp.append(j)
            elif j==0:
                temp.append(i)
            else:
                temp.append(0)
        dt.append(temp)

    
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dt[i][j] = dt[i-1][j-1]
            else:
                dt[i][j] = min(dt[i-1][j], dt[i][j-1], dt[i-1][j-1]) +1 
    return dt[m][n]

标签: none

已有 3 条评论

  1. Amoxicillin Apple Cider Vinegar Cialis Andorra Sin Receta Nonprescription Orlistat cheapest finasteride on the web Zithromax Gynecology

  2. Buying Viagra In Spain cialis overnight shipping from usa Canadian Ed Meds Canada Pills

  3. We offer you the opportunity to advertise your products and services.
    Ciao! Look at an amazing offering for you. I can help you with sending your commercial offers or messages through feedback forms. The advantage of this method is that the messages sent through the feedback forms are included in the white list. This method increases the chance that your message will be read. The same way you received this message.

    Sending via Feedback Forms to any domain zones of the world. (more than 1000 domain zones.).

    The cost of sending 1 million messages is $ 49 instead of $ 99.
    All us sites that have a feedback form. (10 million messages sent) - $349 instead of $649
    Domain zone .com - (12 million messages sent) - $399 instead of $699
    All domain zones in Europe- (8 million messages sent) - $ 299 instead of $599
    All sites in the world (25 million messages sent) - $499 instead of $999

    Discounts are valid until April 7!
    Feedback and warranty!
    Delivery report!

    In the process of sending messages, we do not violate the rules of GDRP.
    This message is created automatically use our contacts for communication.

    Contact us.
    Telegram - @FeedbackFormEU
    Skype – FeedbackForm2019
    Email - feedbackform@make-success.com

    Thank you for your attention.

添加新评论