dynamic_programming.edit_distance

Author : Turfa Auliarachman Date : October 12, 2016

This is a pure Python implementation of Dynamic Programming solution to the edit distance problem.

The problem is : Given 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.

Attributes

solver

Classes

EditDistance

Use :

Module Contents

class dynamic_programming.edit_distance.EditDistance

Use : solver = EditDistance() editDistanceResult = solver.solve(firstString, secondString)

__min_dist_top_down_dp(m: int, n: int) → int

min_dist_bottom_up(word1: str, word2: str) → int

>>> EditDistance().min_dist_bottom_up("intention", "execution")
5
>>> EditDistance().min_dist_bottom_up("intention", "")
9
>>> EditDistance().min_dist_bottom_up("", "")
0

min_dist_top_down(word1: str, word2: str) → int

>>> EditDistance().min_dist_top_down("intention", "execution")
5
>>> EditDistance().min_dist_top_down("intention", "")
9
>>> EditDistance().min_dist_top_down("", "")
0

dp = []

word1 = ''

word2 = ''

dynamic_programming.edit_distance.solver