Decode a Message of Letter-Scrambled Words Against a Known Word List
Company: Cresta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A message was encoded word by word: the letters inside each word were rearranged, while the order of the words and the single spaces between them were left unchanged. You are given the list of known words the original message was written with, and the encoded message. Decode it: for every encoded word, find the known words it could have come from.
A known word is a possible decoding of an encoded word when the two contain exactly the same letters, each the same number of times. Known words can be rearrangements of one another (for example `listen` and `silent`), so one encoded word can have more than one possible decoding, and your function must report all of them.
### Function Signature
```python
def decode_candidates(known_words: list[str], message: str) -> list[list[str]]:
```
### Rules
- The encoded words in `message` are separated by single spaces, with no leading or trailing space.
- An encoded word that is identical to a known word still decodes to it: leaving every letter in place is one of the possible rearrangements.
- Return one list per encoded word, in the order the words appear in `message`. An encoded word that appears several times gets its own list each time.
- Each list contains every known word that is a possible decoding, without duplicates, sorted in ascending lexicographic order.
### Constraints
- `1 <= len(known_words) <= 1000`, and the known words are distinct
- `message` contains between 1 and 1000 encoded words, so `len(message) <= 20999`
- every known word and every encoded word has 1 to 20 characters, all lowercase English letters `a` to `z`
- every encoded word has at least one possible decoding
### Examples
**Example 1**
```text
Input: known_words = ["hello", "world", "code"], message = "olleh dlrow edoc"
Output: [["hello"], ["world"], ["code"]]
```
Each encoded word is a rearrangement of exactly one known word.
**Example 2**
```text
Input: known_words = ["listen", "silent", "stone", "notes", "tones", "tea"], message = "enlist eat noets"
Output: [["listen", "silent"], ["tea"], ["notes", "stone", "tones"]]
```
`enlist` has the same letters as both `listen` and `silent`, and `noets` the same letters as `notes`, `stone` and `tones`, so those lists hold several words in sorted order.
**Example 3**
```text
Input: known_words = ["ab", "ba", "abc"], message = "ba cab ab"
Output: [["ab", "ba"], ["abc"], ["ab", "ba"]]
```
`ba` decodes to itself as well as to `ab`, and the repeated pair of letters gets a separate list at each position.
Overview: Decode a message whose words each had their letters rearranged, using a list of known words that may include anagrams of one another. For every encoded word, return all the known words it could have come from in sorted order, testing letter-count keys, hashing and the handling of ambiguous anagram matches.
Read the full Cresta Software Engineer interview experience this question came from
A message was encoded word by word: the letters inside each word were rearranged, while the order of the words and the single spaces between them were left unchanged. You are given `known_words`, the list of known words the original message was written with, and the encoded `message`. Decode it: for every encoded word, find the known words it could have come from.
A known word is a possible decoding of an encoded word when the two contain exactly the same letters, each the same number of times. Known words can be rearrangements of one another (for example `listen` and `silent`), so one encoded word can have more than one possible decoding, and your function must report all of them.
Implement `decode_candidates(known_words, message)`, which returns a list of lists of strings:
- The encoded words in `message` are separated by single spaces, with no leading or trailing space.
- An encoded word that is identical to a known word still decodes to it: leaving every letter in place is one of the possible rearrangements.
- Return one list per encoded word, in the order the words appear in `message`. An encoded word that appears several times gets its own list each time.
- Each list contains every known word that is a possible decoding, without duplicates, sorted in ascending lexicographic order.
Only strings and lists of strings are passed in and returned; no numeric value is involved.
### Example 1
```text
Input: known_words = ["listen", "silent", "stone", "notes", "tones", "tea"], message = "enlist eat noets"
Output: [["listen", "silent"], ["tea"], ["notes", "stone", "tones"]]
```
`enlist` has the same letters as both `listen` and `silent`, `eat` the same letters as `tea`, and `noets` the same letters as `notes`, `stone` and `tones`, so those lists hold several words in sorted order.
### Example 2
```text
Input: known_words = ["ab", "ba", "abc"], message = "ba cab ab"
Output: [["ab", "ba"], ["abc"], ["ab", "ba"]]
```
`ba` decodes to itself as well as to `ab`, and the repeated pair of letters gets a separate list at each position.
### Constraints
- `1 <= len(known_words) <= 1000`, and the known words are distinct
- `message` contains between 1 and 1000 encoded words, so `len(message) <= 20999`
- every known word and every encoded word has 1 to 20 characters, all lowercase English letters `a` to `z`
- every encoded word has at least one possible decoding
Constraints
- 1 <= len(known_words) <= 1000, and the known words are distinct
- message contains between 1 and 1000 encoded words, separated by single spaces with no leading or trailing space, so len(message) <= 20999
- Every known word and every encoded word has 1 to 20 characters, all lowercase English letters a to z
- Every encoded word has at least one possible decoding
Examples
Input: (['a'], 'a')
Expected Output: [['a']]
Explanation: Minimum valid input: one known word and a message made of one one-letter encoded word.
Input: (['hello', 'world', 'code'], 'olleh dlrow edoc')
Expected Output: [['hello'], ['world'], ['code']]
Explanation: Source example 1: each scrambled word is a rearrangement of exactly one known word.
Hints
- Rearranging the letters of a word never changes how many times each letter appears in it, and two words with the same letter counts can always be rearranged into each other.
- The same encoded word, or two different encoded words with the same letters, can appear at several positions; each position still needs its own list, in message order.
- Every list must be in ascending lexicographic order regardless of the order of known_words, and an encoded word identical to a known word still counts as a decoding of it.