@@ -0,0 +1,2092 @@
+%22%22%22%0AAuthor  : Turfa Auliarachman%0ADate    : October 12, 2016%0A%0AThis is a pure Python implementation of Dynamic Programming solution to the edit distance problem.%0A%0AThe problem is :%0AGiven two strings A and B. Find the minimum number of operations to string B such that A = B. The permitted operations are removal,  insertion, and substitution.%0A%22%22%22%0A%0Aclass EditDistance:%0A    %22%22%22%0A    Use :%0A    solver              = EditDistance()%0A    editDistanceResult  = solver.solve(firstString, secondString)%0A    %22%22%22%0A%0A    def __init__(self):%0A        self.__prepare__()%0A%0A    def __prepare__(self, N = 0, M = 0):%0A        self.dp = %5B%5B-1 for y in range(0,M)%5D for x in range(0,N)%5D%0A%0A    def __solveDP(self, x, y):%0A        if (x==-1):%0A            return y+1%0A        elif (y==-1):%0A            return x+1%0A        elif (self.dp%5Bx%5D%5By%5D%3E-1):%0A            return self.dp%5Bx%5D%5By%5D%0A        else:%0A            if (self.A%5Bx%5D==self.B%5By%5D):%0A                self.dp%5Bx%5D%5By%5D = self.__solveDP(x-1,y-1)%0A            else:%0A                self.dp%5Bx%5D%5By%5D = 1+min(self.__solveDP(x,y-1), self.__solveDP(x-1,y), self.__solveDP(x-1,y-1))%0A%0A            return self.dp%5Bx%5D%5By%5D%0A%0A    def solve(self, A, B):%0A        if isinstance(A,bytes):%0A            A = A.decode('ascii')%0A%0A        if isinstance(B,bytes):%0A            B = B.decode('ascii')%0A%0A        self.A = str(A)%0A        self.B = str(B)%0A%0A        self.__prepare__(len(A), len(B))%0A%0A        return self.__solveDP(len(A)-1, len(B)-1)%0A%0Aif __name__ == '__main__':%0A        import sys%0A        if sys.version_info.major %3C 3:%0A            input_function = raw_input%0A        else:%0A            input_function = input%0A%0A        solver = EditDistance()%0A%0A        print(%22****************** Testing Edit Distance DP Algorithm ******************%22)%0A        print()%0A%0A        print(%22Enter the first string: %22, end=%22%22)%0A        S1 = input_function()%0A%0A        print(%22Enter the second string: %22, end=%22%22)%0A        S2 = input_function()%0A%0A        print()%0A        print(%22The minimum Edit Distance is: %25d%22 %25 (solver.solve(S1, S2)))%0A        print()%0A        print(%22*************** End of Testing Edit Distance DP Algorithm ***************%22)%0A

Add Edit Distance DP Algorithm