Word break

Questions 1 to 5 of 7

1. 1. In the word break table ok, why is ok[0] set to true?

   ok[0] is false, because an empty string cannot be splitok[0] is true, because the dictionary always contains the empty wordok[0] is true, because the empty prefix splits into zero words, and every later true value is built from earlier true valuesok[0] is never read, so its value does not matter
2. 2. Why does can_break_max_len start its inner loop at end - 1 and stop at lowest?

   Python's slice s[start:end] cannot read backwardsThe table is filled from right to leftThe first letter of every word must be checked firstA piece longer than the longest word cannot be in the dictionary, so starts before lowest need no check
3. 3. What does this program print? ``python work = 0 def can_break_max_len(s, words): global work dictionary = set(words) max_len = max(len(w) for w in words) ok = [False] * (len(s) + 1) ok[0] = True for end in range(1, len(s) + 1): lowest = max(0, end - max_len) for start in range(end - 1, lowest - 1, -1): work += 1 if ok[start] and s[start:end] in dictionary: ok[end] = True break return ok[len(s)] print(f"{can_break_max_len('aaa', ['a', 'aa'])} work={work}") ``

   True work=6True work=3False work=3True work=1
4. 4. What does this program print? ``python class TrieNode: def __init__(self): self.next = {} self.is_word = False def build_trie(words): root = TrieNode() for w in words: node = root for c in w: if c not in node.next: node.next[c] = TrieNode() node = node.next[c] node.is_word = True return root def split_one(s, words): root = build_trie(words) n = len(s) came_from = [-1] * (n + 1) came_from[0] = 0 for start in range(n): if came_from[start] == -1: continue node = root for i in range(start, n): node = node.next.get(s[i]) if node is None: break if node.is_word and came_from[i + 1] == -1: came_from[i + 1] = start if came_from[n] == -1: return [] result = [] end = n while end > 0: start = came_from[end] result.insert(0, s[start:end]) end = start return result print(split_one('catsdog', ['cat', 'cats', 'dog'])) ``

   ['cats', 'dog']['cat', 'dog']['cat', 's', 'dog']['catsdog']
5. 5. A string has 2000 letters, and every single letter is a word in the dictionary. The longest word has 4 letters. How many times does work += 1 run in can_break_max_len?

   Type a number.