Two-Dimensional DP

dp[i][j] over prefixes

Problems over two strings or a grid use a 2-D state: dp[i][j] is the answer for the first i characters of a and the first j of b. Edit distance takes the minimum of insert, delete or replace when characters differ; longest common subsequence extends a match diagonally or takes the better of skipping a character. Because each row depends only on the previous one, memory can drop from O(m·n) to O(n).

Edit distance and LCS, run

I ran this with Python 3.12.3 (standard library only). horse to ros needs 3 edits and intention to execution needs 5; abcde and ace share a subsequence of length 3, while abc and def share none.

# 2-D dynamic programming: edit distance and longest common subsequence
def edit_distance(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        dp[i][0] = i
    for j in range(len(b) + 1):
        dp[0][j] = j
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[-1][-1]

def lcs(a, b):
    prev = [0] * (len(b) + 1)             # rolling row: O(len(b)) memory
    for ch in a:
        cur = [0]
        for j, bj in enumerate(b, 1):
            cur.append(prev[j - 1] + 1 if ch == bj else max(prev[j], cur[j - 1]))
        prev = cur
    return prev[-1]

print(edit_distance("horse", "ros"), edit_distance("intention", "execution"))
print(lcs("abcde", "ace"), lcs("abc", "def"))

Output:

3 5
3 0

Draw a small table

Filling a 3 by 4 table by hand on the whiteboard makes the transition clear to you and the interviewer.

त्वरित जाँच: What does dp[i][j] mean in edit distance?

• The length of a
• The number of matching characters
• The minimum edits to turn the first i characters of a into the first j of b
• The index of the first mismatch