The say encoding of a string of digits splits it into maximal runs of equal digits and writes, for each run, its length in decimal followed by the digit. Runs are at most 99 long, so a length takes one or two characters.
say("7") # "17"
say("000") # "30"
say("4444449") # "6419"
say("5" * 12) # "125" twelve 5s: the length "12" then the digit "5"
say("") # ""
Decoding is ambiguous, because you can't tell whether a length has one digit or two. Implement decode_all(encoded: str) -> list[str]: every digit string t with say(t) == encoded, sorted ascending, with no duplicates. Return [] if there is none, and [""] for the empty input.
Reading encoded left to right as (length, digit) chunks, a decoding is valid only if:
- every length is
1..99written without a leading zero ("0"and"07"are not lengths); - two consecutive chunks have different digits, since
saywould have merged them into one run.
decode_all("11213")
# ["1" + "3" * 21, "2" * 11 + "3"] chunks 1|1 21|3 or 11|2 1|3
decode_all("1112") # ["12"] 1|1 1|2 works; 11|1 leaves a lone "2"
decode_all("2525") # [] 2|5 2|5 repeats the digit 5; 25|2 leaves a lone "5"
decode_all("105") # ["5" * 10]
decode_all("000") # []
encoded has at most 100 characters and at most a few thousand valid decodings, but it can have astronomically many partial readings that die near the end. Plain backtracking that retries the same suffix again and again is too slow.
Show hint
Whether the suffix starting at index i can still be decoded depends only on i and the previous chunk's digit. Memoize that yes/no answer, and let the backtracking only follow chunks whose suffix is decodable.