Find Every Reachable Derived Vocabulary Word
Duolingo● MediumINTERNPHONE SCREENProblem statement
A word directly derives from another word when it can be formed by rearranging all of that word's letters and adding exactly one new letter. Letters are counted with multiplicity: no existing letter may be removed or replaced.
Given start and vocabulary, return every vocabulary word reachable from start through one or more direct derivations.
For this exercise, assume every intermediate and resulting word after start must be listed in vocabulary. The start need not be listed. Equal-length anagrams of start are not derivatives because every step adds one letter.
For this exercise, assume vocabulary labels are unique and all words are nonempty lowercase English strings of length at most 12. Return each reachable label once in lexicographic order; an empty vocabulary returns an empty array.
Function
deriveVocabulary(start: String, vocabulary: String[]) → String[]Examples
Example 1
start = "two"vocabulary = ["wout"]return = ["wout"]The reported relation two to wout is preserved: rearrange and add u. This vocabulary wrapper is authored.
Example 2
start = "two"vocabulary = ["woutx","two"]return = []This authored example has no listed intermediate of length four, so woutx is unreachable under the declared vocabulary-step rule.
Example 3
start = "ab"vocabulary = ["abcd","acb","abc","bca"]return = ["abc","abcd","acb","bca"]This authored example reaches three anagrams directly and abcd through a listed length-three intermediate.
Constraints
- For this exercise, assume
0 <= vocabulary.length <= 200. 1 <= start.length, vocabulary[i].length <= 12; every character is a lowercase English letter.- Vocabulary words are unique, and every intermediate after start must be a vocabulary word.