https://leetcode.com/problems/edit-distance/

edit_dist_72.py

# Edit distance problem

class Solution(object):

    def minDistance_recursive(self, word1, word2):
        """
        Recursive solution
        :type word1: str
        :type word2: str
        :rtype: int
        """
        cache = {}

        def score(i, j):
            if (i, j) not in cache:
                # Base case
                if i == 0 or j == 0:
                    return max(i, j)

                # Get the chars at positions
                c1, c2 = word1[i - 1], word2[j - 1]

                top_left = score(i-1, j-1) + (c1 != c2)
                top = score(i-1, j) + 1
                left = score(i, j-1) + 1
                cache[i, j] = min(top_left, top, left)
            return cache[i, j]

        return score(len(word1), len(word2))

    def minDistance(self, word1, word2):
        '''Iterative solution'''
        scores = [[0 for i in range(len(word2)+1)] for j in range(len(word1)+1)]
        for i in range(len(word1) + 1):
            for j in range(len(word2) + 1):
                if i == 0:
                    scores[i][j] = j
                elif j == 0:
                    scores[i][j] = i
                else:
                    c1 = word1[i-1]
                    c2 = word2[j-1]
                    top_left = scores[i-1][j-1] + (c1 != c2)
                    top = scores[i-1][j] + 1
                    left = scores[i][j-1] + 1
                    scores[i][j] = min(top_left, top, left)
        return scores[len(word1)][len(word2)]


if __name__ == '__main__':
    import time

    alphabet = 'abcdefghij'
    sol = Solution()
    size_mults = list(range(0, 100, 10))

    # Iterative
    print("Testing Iterative ---------")
    times_iter = []
    sizes = []
    for i in size_mults:
        w1 = alphabet * i
        w2 = w1
        start_time = time.time()
        sol.minDistance(w1, w2)
        run_time = time.time() - start_time
        print("size: {}    time: {}".format(len(w1), run_time))
        sizes.append(len(w1))
        times_iter.append(run_time)

    # Recursive
    print("Testing Recursive ---------")
    times_recursive = []
    for i in size_mults:
        w1 = alphabet * i
        w2 = w1
        start_time = time.time()
        sol.minDistance_recursive(w1, w2)
        run_time = time.time() - start_time
        print("size: {}    time: {}".format(len(w1), run_time))
        times_recursive.append(run_time)

    import pandas as pd
    df = pd.DataFrame({
        'size': sizes,
        'iterative': times_iter,
        'recursive': times_recursive})
    df['const_factor'] = df['recursive'] / df['iterative']
    print(df)


# Testing Iterative ---------
# size: 0    time: 1.811981201171875e-05
# size: 100    time: 0.00892782211303711
# size: 200    time: 0.034729957580566406
# size: 300    time: 0.08474302291870117
# size: 400    time: 0.14288902282714844
# size: 500    time: 0.2287600040435791
# size: 600    time: 0.32260608673095703
# size: 700    time: 0.44570207595825195
# size: 800    time: 0.5894551277160645
# size: 900    time: 0.7515249252319336
# Testing Recursive ---------
# size: 0    time: 9.059906005859375e-06
# size: 100    time: 0.015774965286254883
# size: 200    time: 0.07314896583557129
# size: 300    time: 0.18871593475341797
# size: 400    time: 0.340681791305542
# size: 500    time: 0.5974040031433105
# size: 600    time: 0.9015798568725586
# size: 700    time: 1.38783597946167
# size: 800    time: 1.9424901008605957
# size: 900    time: 2.7101988792419434
#    iterative  recursive  size  const_factor
# 0   0.000018   0.000009     0      0.500000
# 1   0.008928   0.015775   100      1.766944
# 2   0.034730   0.073149   200      2.106221
# 3   0.084743   0.188716   300      2.226920
# 4   0.142889   0.340682   400      2.384240
# 5   0.228760   0.597404   500      2.611488
# 6   0.322606   0.901580   600      2.794677
# 7   0.445702   1.387836   700      3.113820
# 8   0.589455   1.942490   800      3.295399
# 9   0.751525   2.710199   900      3.606266