The diff algorithm Git uses(my Python version beats 99.75%)


  • 0
    J

    Please Google "myers diff algorithm"!
    I wrote the code about one year ago and don't know what the hack is going now. Sorry...
    As I know, it is fastest discovered LCS algorithm.

    class Solution:
        def minDistance(self, word1, word2):
            """
            :type word1: str
            :type word2: str
            :rtype: int
            """
            return (len(word1) + len(word2) - self.diff(word1, word2))
    
        def diff(self, a, b):
            max_supply = len(a) + len(b)
            max_x_nth_k = {1: 0}
    
            for supply in range(max_supply + 1):
                for nth_k in range(-supply, supply + 1, 2):
                    if nth_k == -supply or (nth_k != supply and max_x_nth_k[nth_k - 1] < max_x_nth_k[nth_k + 1]):
                        x = max_x_nth_k[nth_k + 1]
                    else:
                        x = max_x_nth_k[nth_k - 1] + 1
                    y = x - nth_k
    
                    while x < len(a) and y < len(b) and a[x] == b[y]:
                        x += 1
                        y += 1
                    max_x_nth_k[nth_k] = x
    
                    if x >= len(a) and y >= len(b):
                        return (len(a) + len(b) - supply) // 2
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.