A message arrived with all its spaces stripped out. Given the stripped text s and a dictionary words, write all_readings(s: str, words: list[str]) -> list[str] that returns every way to split s into dictionary words, each written as those words joined by single spaces.
- A dictionary word may be used any number of times.
- The readings can come back in any order; each must appear once. Return
[]if there is no reading.
all_readings("sunflowerseed", ["sun", "flower", "sunflower", "flowers", "seed", "see", "d", "ed"])
# ["sun flower see d", "sun flower seed", "sunflower see d", "sunflower seed"] in some order
# ("flowers" leads nowhere: nothing in the dictionary spells "eed")
all_readings("aaa", ["a", "aa"]) # ["a a a", "a aa", "aa a"]
all_readings("catfish", ["cat", "dog"]) # []
Constraints:
1 <= len(s) <= 200;1 <= len(words) <= 500; each word is 1 to 10 letters; the words are distinct; everything is lowercase.- The answer has at most 5,000 readings.
Inputs can be much harder than their answers: "aaa...ab" with the dictionary ["a", "aa", "aaa"] has no reading at all, yet there are astronomically many ways to split the as before discovering the b is stuck. Aim for time roughly O(n · L + size of the answer), where L is the longest word length, including when the answer is empty.
Show hint
first work out, for every position i, whether the tail s[i:] can be split into words at all (from the end backwards, each position looks at most L letters ahead). Then build readings from the front, but only ever step to positions whose tail can finish.