How Edit Distance Works

The class docstring's usage example is terse and prescriptive: instantiate once, call solve with two strings. That design choice is instructive. The class stores word1, word2, and dp as instance attributes rather than function locals so that the private recursive method __min_dist_top_down_dp can read and write the memoization table without receiving it as a parameter. The alternative would be a standalone function with a default-argument dict, which Python's functional DP files often use. Choosing a class here keeps the recursive helper's signature simple: two integer indices m and n. The cost is that calling min_dist_top_down after min_dist_bottom_up on the same instance would overwrite the dp table, so the caller must be aware.

The indices m and n are character positions in word1 and word2 respectively, starting from the last character and counting down. Base cases on lines 27 through 30 handle the empty-prefix situation: if m is -1, the first string is exhausted and we need n + 1 insertions to produce the remainder of the second. The memo check on line 31 returns a previously computed result immediately. When characters match on line 34, no operation is needed and the cost is the cost of the remaining prefixes. When they differ, three recursive calls compute the cost of each allowed operation: advance only n for insert, advance only m for delete, advance both for replace. The minimum plus one is stored in the table on line 40.

Three doctests pin the top-down implementation. ("intention", "execution") has edit distance 5, a standard textbook example: substitute i to e, substitute n to x, insert c, substitute t to u, substitute n to n (no op), substitute i to i (no op) and delete one more n. The empty second string has distance 9 because converting a 9-character string to the empty string costs 9 deletions. Two empty strings cost 0. Line 55 builds the memo table as a two-dimensional list filled with -1 sentinels, one for each pair of character positions. Line 57 starts the recursion at the last indices of both strings, which is the natural top-down entry point for a suffix-based recursion.

The bottom-up method computes the same three doctests as the top-down version because both implement the same Levenshtein recurrence. The structural difference is initialization. The top-down table uses -1 as a memo sentinel and base cases live in the recursive function. The bottom-up table on line 72 is (m+1) by (n+1) with an extra row and column for empty-prefix base cases, filled explicitly in the loop. Row 0 (i == 0) gets value j: converting an empty string to a j-character string requires j insertions. Column 0 (j == 0) gets value i: deleting all i characters from the first string to reach empty. The three-way min at lines 83 through 86 is the recurrence, identical in logic to the recursive version. Reading self.dp[m][n] at the end gives the answer without a traceback because only the length is returned, not the sequence of operations.

The interactive driver is also a consistency check. A single EditDistance instance is created on line 91, both input strings are collected with .strip() on lines 96 and 97, and then both methods are called on lines 100 and 101. When both methods are working correctly they must produce identical output for any pair of strings, because they compute the same mathematical quantity by different means. A user who types the same two strings repeatedly and sees both lines print the same number has informal confirmation that neither implementation is broken. The separation of top-down and bottom-up in a single class is the pedagogical payoff of the class design: a learner can compare the two approaches side by side, run both, and verify the answers match.