Use : solver = EditDistance() editDistanceResult = solver.solve(firstString, secondString)
| 11 | |
| 12 | |
| 13 | class EditDistance: |
| 14 | """ |
| 15 | Use : |
| 16 | solver = EditDistance() |
| 17 | editDistanceResult = solver.solve(firstString, secondString) |
| 18 | """ |
| 19 | |
| 20 | def __init__(self): |
| 21 | self.__prepare__() |
| 22 | |
| 23 | def __prepare__(self, N = 0, M = 0): |
| 24 | self.dp = [[-1 for y in range(0,M)] for x in range(0,N)] |
| 25 | |
| 26 | def __solveDP(self, x, y): |
| 27 | if (x==-1): |
| 28 | return y+1 |
| 29 | elif (y==-1): |
| 30 | return x+1 |
| 31 | elif (self.dp[x][y]>-1): |
| 32 | return self.dp[x][y] |
| 33 | else: |
| 34 | if (self.A[x]==self.B[y]): |
| 35 | self.dp[x][y] = self.__solveDP(x-1,y-1) |
| 36 | else: |
| 37 | self.dp[x][y] = 1+min(self.__solveDP(x,y-1), self.__solveDP(x-1,y), self.__solveDP(x-1,y-1)) |
| 38 | |
| 39 | return self.dp[x][y] |
| 40 | |
| 41 | def solve(self, A, B): |
| 42 | if isinstance(A,bytes): |
| 43 | A = A.decode('ascii') |
| 44 | |
| 45 | if isinstance(B,bytes): |
| 46 | B = B.decode('ascii') |
| 47 | |
| 48 | self.A = str(A) |
| 49 | self.B = str(B) |
| 50 | |
| 51 | self.__prepare__(len(A), len(B)) |
| 52 | |
| 53 | return self.__solveDP(len(A)-1, len(B)-1) |
| 54 | |
| 55 | if __name__ == '__main__': |
| 56 | try: |