Harder two-sequence transitions

The same table as before, with transitions that need real care about what each branch means.

Key idea

Counting how many ways one sequence appears inside another

The state is the same pair of prefixes. The answer at (i, j) is how many ways the first j characters of the target appear as a subsequence within the first i characters of the source.

The transition splits on the last source character. It can always be ignored, which contributes the count at (i-1, j). If it matches the target's last character, it can also be used, which contributes the count at (i-1, j-1).

Both branches are added rather than maximized, because they are different ways rather than competing options. That is the difference from the earlier lesson and it is easy to carry over wrongly.

1def appearances(source, target):2    ways = [[0] * (len(target) + 1) for _ in range(len(source) + 1)]3    for i in range(len(source) + 1):4        ways[i][0] = 1                       # one way to match nothing5 6    for i in range(1, len(source) + 1):7        for j in range(1, len(target) + 1):8            ways[i][j] = ways[i - 1][j]                      # skip this character9            if source[i - 1] == target[j - 1]:10                ways[i][j] += ways[i - 1][j - 1]             # or use it11    return ways[len(source)][len(target)]12 13print(appearances("rabbbit", "rabbit"))14print(appearances("abc", ""), appearances("", "a"))

Key idea

Measuring how different two sequences are

A different question on the same table: the fewest single-character edits turning one sequence into another, where an edit inserts, removes, or replaces one character.

If the last characters match, nothing needs doing and the answer is the answer for both prefixes shortened. If they differ, one edit must happen and the three kinds correspond to the three neighbors.

Naming the three neighbors is the thing to get right, so here they are for one mismatching cell.

1a, b = "horse", "ros"2i, j = 1, 1                            # the prefixes "h" and "r"3 4print("last characters:", a[i - 1], "and", b[j - 1], "-> mismatch")5print("diagonal (i-1, j-1): replace", a[i - 1], "with", b[j - 1])6print("up       (i-1, j)  : delete", a[i - 1], "from the first")7print("left     (i, j-1)  : insert", b[j - 1], "into the first")

One edit is unavoidable here, so all three cost one plus whatever that neighbor already costs.

Predict the output· 5 min

Predict the output: a zeroed base column

This counts appearances but initializes the whole table to zeros without setting the empty-target column. Type the two values it prints.

Python

1def appearances_broken(source, target):2    ways = [[0] * (len(target) + 1) for _ in range(len(source) + 1)]3    for i in range(1, len(source) + 1):4        for j in range(1, len(target) + 1):5            ways[i][j] = ways[i - 1][j]6            if source[i - 1] == target[j - 1]:7                ways[i][j] += ways[i - 1][j - 1]8    return ways[len(source)][len(target)]9 10def appearances(source, target):11    ways = [[0] * (len(target) + 1) for _ in range(len(source) + 1)]12    for i in range(len(source) + 1):13        ways[i][0] = 114    for i in range(1, len(source) + 1):15        for j in range(1, len(target) + 1):16            ways[i][j] = ways[i - 1][j]17            if source[i - 1] == target[j - 1]:18                ways[i][j] += ways[i - 1][j - 1]19    return ways[len(source)][len(target)]20 21print(appearances_broken("rabbbit", "rabbit"), appearances("rabbbit", "rabbit"))

Printed output

Problem· 30 min

Distinct Subsequences

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

Problem· 30 min

Edit Distance

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

1def appearances(source, target):2 ways = [[0] * (len(target) + 1) for _ in range(len(source) + 1)]3 for i in range(len(source) + 1):4 ways[i][0] = 1 # one way to match nothing5 6 for i in range(1, len(source) + 1):7 for j in range(1, len(target) + 1):8 ways[i][j] = ways[i - 1][j] # skip this character9 if source[i - 1] == target[j - 1]:10 ways[i][j] += ways[i - 1][j - 1] # or use it11 return ways[len(source)][len(target)]12 13print(appearances("rabbbit", "rabbit"))14print(appearances("abc", ""), appearances("", "a"))

1a, b = "horse", "ros"2i, j = 1, 1 # the prefixes "h" and "r"3 4print("last characters:", a[i - 1], "and", b[j - 1], "-> mismatch")5print("diagonal (i-1, j-1): replace", a[i - 1], "with", b[j - 1])6print("up (i-1, j) : delete", a[i - 1], "from the first")7print("left (i, j-1) : insert", b[j - 1], "into the first")

1def appearances_broken(source, target):2 ways = [[0] * (len(target) + 1) for _ in range(len(source) + 1)]3 for i in range(1, len(source) + 1):4 for j in range(1, len(target) + 1):5 ways[i][j] = ways[i - 1][j]6 if source[i - 1] == target[j - 1]:7 ways[i][j] += ways[i - 1][j - 1]8 return ways[len(source)][len(target)]9 10def appearances(source, target):11 ways = [[0] * (len(target) + 1) for _ in range(len(source) + 1)]12 for i in range(len(source) + 1):13 ways[i][0] = 114 for i in range(1, len(source) + 1):15 for j in range(1, len(target) + 1):16 ways[i][j] = ways[i - 1][j]17 if source[i - 1] == target[j - 1]:18 ways[i][j] += ways[i - 1][j - 1]19 return ways[len(source)][len(target)]20 21print(appearances_broken("rabbbit", "rabbit"), appearances("rabbbit", "rabbit"))