When the state is a position in a string

The answer at each position depends on how the piece ending there could have been formed.

Why it works

Each rule contributes one term

To reach position i, the last piece consumed must have been of some allowed length. Each allowed length contributes the count from wherever that piece started.

So write one term per rule, each guarded by whether that piece is actually valid here. The recurrence is a sum of the terms whose guards pass.

1def ways_to_split(text, allowed):2    """Ways to cut text into consecutive pieces, all of them allowed."""3    counts = [0] * (len(text) + 1)4    counts[0] = 1                            # one way to consume nothing5 6    for i in range(1, len(text) + 1):7        for piece in allowed:8            start = i - len(piece)9            if start >= 0 and text[start:i] == piece:10                counts[i] += counts[start]11    return counts[len(text)]12 13print(ways_to_split("aab", {"a", "aa", "b"}))14print(ways_to_split("aab", {"a", "b"}))15print(ways_to_split("xyz", {"a"}))

Predict the output· 5 min

Predict the output: which pieces are legal at each position

A digit string is scanned, and at each position the one and two character pieces ending there are tested against a set of legal codes. Type the four lines it prints.

Python

1legal = {str(n) for n in range(1, 27)}2text = "226"3 4for i in range(1, len(text) + 1):5    one = text[i - 1:i]6    two = text[i - 2:i] if i >= 2 else ""7    options = [piece for piece in (one, two) if piece in legal]8    print("ending at", i, "->", options)9 10print("note:", "06" in legal, "6" in legal)

Printed output

Problem· 28 min

Decode Ways

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 ways_to_split(text, allowed):2 """Ways to cut text into consecutive pieces, all of them allowed."""3 counts = [0] * (len(text) + 1)4 counts[0] = 1 # one way to consume nothing5 6 for i in range(1, len(text) + 1):7 for piece in allowed:8 start = i - len(piece)9 if start >= 0 and text[start:i] == piece:10 counts[i] += counts[start]11 return counts[len(text)]12 13print(ways_to_split("aab", {"a", "aa", "b"}))14print(ways_to_split("aab", {"a", "b"}))15print(ways_to_split("xyz", {"a"}))

1legal = {str(n) for n in range(1, 27)}2text = "226"3 4for i in range(1, len(text) + 1):5 one = text[i - 1:i]6 two = text[i - 2:i] if i >= 2 else ""7 options = [piece for piece in (one, two) if piece in legal]8 print("ending at", i, "->", options)9 10print("note:", "06" in legal, "6" in legal)