Word Break and Decode Ways
28 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)When the input is a string, the state is often how many characters are done. The last piece, a word or one or two digits, decides how a cell uses the earlier cells.
States that are prefixes of a string
A prefix state is a table cell for the first i characters of a string, with i from 0 to n. Cell 0 stands for the empty prefix and is the base case.
Some tables are indexed by how much of a string is done. Let dp[i] be the answer for the first i characters. The next cell looks back at the last piece that could end at i.
s = "apple"dp = [True] + [False] * len(s)print(len(dp), dp[0])A string of length n gives n + 1 cells, because the empty prefix is a state too. dp[0] is the base case: nothing is left to explain.
Word break
A string and a list of allowed words are given. Can the string be cut into words from the list? dp[i] is True when some word ends exactly at i and the part before it was already True.
def word_break(s, words): words = set(words) dp = [True] + [False] * len(s) for i in range(1, len(s) + 1): for j in range(i): if dp[j] and s[j:i] in words: dp[i] = True break return dp[len(s)]
print(word_break("applepenapple", ["apple", "pen"]))Example 1 · Which prefixes can be built
s = "catsanddog"words = {"cat", "cats", "and", "sand", "dog"}dp = [True] + [False] * len(s)for i in range(1, len(s) + 1): dp[i] = any(dp[j] and s[j:i] in words for j in range(i))print([i for i in range(len(s) + 1) if dp[i]])[0, 3, 4, 7, 10]
What this code does
- The True cells are the lengths of prefixes that can be cut into words: 0, 3, 4, 7 and 10.
any(...)stops at the first True, like thebreakin a loop.
Example 2 · Limit the piece length
def word_break(s, words): words = set(words) longest = max(map(len, words)) dp = [True] + [False] * len(s) for i in range(1, len(s) + 1): for j in range(max(0, i - longest), i): if dp[j] and s[j:i] in words: dp[i] = True break return dp[len(s)]
print(word_break("abcabcabc", ["abc", "ab"]))print(word_break("abcd", ["abc", "ab"]))True False
What this code does
- No word is longer than
longest, so only the lastlongeststart positions need checking. - The time falls from O(n^2) to O(n x longest).
A set makes the word test O(1) on average, plus the cost of slicing. Time is O(n^2) slices and space is O(n). If the longest word has length m, loop j from i - m to i - 1 to make it O(n x m).
Counting ways to cut
Counting cuts is a prefix table where dp[i] adds dp[j] for every word that ends at i and starts at j, with dp[0] = 1.
To count the ways instead of testing, add instead of setting True. Each cell sums the cells where a word can start. The same shape as coin change appears: the last piece is the choice.
def count_cuts(s, words): words = set(words) dp = [1] + [0] * len(s) for i in range(1, len(s) + 1): for j in range(i): if s[j:i] in words: dp[i] += dp[j] return dp[len(s)]
print(count_cuts("aaaa", ["a", "aa"]))Example 3 · Count the cuts
def count_cuts(s, words): words = set(words) dp = [1] + [0] * len(s) for i in range(1, len(s) + 1): for j in range(i): if s[j:i] in words: dp[i] += dp[j] return dp[len(s)]
print(count_cuts("catsanddog", ["cat", "cats", "and", "sand", "dog"]))print(count_cuts("a" * 20, ["a", "aa"]))2 10946
What this code does
- The first string has two cuts: cat-sand-dog and cats-and-dog.
- A string of 20 a's has 10946 cuts. That is the Fibonacci numbers again.
For "aaaa" there are 5 cuts: a-a-a-a, a-aa-a, aa-a-a, a-a-aa and aa-aa. The count can grow quickly, but Python integers do not overflow.
Decode ways
Codes 1 to 26 stand for letters. A string of digits can be read in several ways. A cell uses one digit if it is not 0, and two digits if they make 10 to 26. Zero alone is never valid.
def decode(s): if not s or s[0] == "0": return 0 dp = [1, 1] + [0] * (len(s) - 1) for i in range(2, len(s) + 1): if s[i - 1] != "0": dp[i] += dp[i - 1] if 10 <= int(s[i - 2:i]) <= 26: dp[i] += dp[i - 2] return dp[len(s)]
print(decode("226"))Example 4 · Decode table
s = "11106"dp = [1, 1] + [0] * (len(s) - 1)for i in range(2, len(s) + 1): if s[i - 1] != "0": dp[i] += dp[i - 1] if 10 <= int(s[i - 2:i]) <= 26: dp[i] += dp[i - 2]print(dp)[1, 1, 2, 3, 2, 2]
What this code does
- The last digit 6 can stand alone, and 06 is not a valid pair, so only dp[4] is carried.
- The 0 cannot stand alone, so dp[4] comes only from the pair 10 and equals dp[2].
Example 5 · Bad codes
def decode(s): if not s or s[0] == "0": return 0 dp = [1, 1] + [0] * (len(s) - 1) for i in range(2, len(s) + 1): if s[i - 1] != "0": dp[i] += dp[i - 1] if 10 <= int(s[i - 2:i]) <= 26: dp[i] += dp[i - 2] return dp[len(s)]
for code in ["12", "06", "30", "100", "2101"]: print(code, decode(code))12 2 06 0 30 0 100 0 2101 1
What this code does
"06"and"30"and"100"have no valid reading, because a zero needs a 1 or 2 before it."2101"is 2-10-1 only, so one way. Test the zeros first; they cause most mistakes.
Example 6 · Decode with two variables
def decode(s): if not s or s[0] == "0": return 0 two, one = 1, 1 for i in range(2, len(s) + 1): now = 0 if s[i - 1] != "0": now += one if 10 <= int(s[i - 2:i]) <= 26: now += two two, one = one, now return one
print(decode("1111111111"))89
What this code does
- Each cell reads only the two before it, so two variables are enough and space is O(1).
- Ten ones can be read in 89 ways, another Fibonacci number.
"226" can be 2-2-6, 22-6 or 2-26, so the answer is 3. A leading zero or a lone zero such as "30" gives 0. Time is O(n) and space is O(n), reducible to two variables.
Next step
Check your understanding
12 quick questions