Keyboard Autocomplete Suggestions
Lyft● MediumNEW GRADONSITE INTERVIEWProblem statement
A phone keyboard suggests words while you type. You are given a dictionary words and the word typed that the user types one letter at a time.
After each letter, the keyboard shows up to three suggestions: the dictionary words that start with the letters typed so far. When more than three words match, it shows the three that come first in alphabetical order. A dictionary word equal to the letters typed so far also counts as a match.
Return a list with one entry per typed letter. Entry i is the list of suggestions after the first i + 1 letters, in alphabetical order. It is empty when no word matches.
Function
autocomplete(words: String[], typed: String) → String[][]Examples
Example 1
words = ["ride","rider","rides","riding","road","rate"]typed = "rid"return = [["rate","ride","rider"],["ride","rider","rides"],["ride","rider","rides"]]After "r", all six words match; the three smallest in alphabetical order are "rate", "ride" and "rider". After "ri", the matches are "ride", "rider", "rides" and "riding", and the first three are shown. "rid" has the same four matches and the same three suggestions.
Example 2
words = ["map","maps","mop"]typed = "maze"return = [["map","maps","mop"],["map","maps"],[],[]]"m" matches all three words. "ma" matches only "map" and "maps", so only two suggestions are shown. No word starts with "maz", so that list is empty, and so is the list for "maze".
Example 3
words = ["gone","go","golf","goal"]typed = "gol"return = [["go","goal","golf"],["go","goal","golf"],["golf"]]A word that is itself a prefix of another word, like "go", comes first in alphabetical order. After "g" and "go", all four words match and the three smallest are "go", "goal" and "golf"; "gone" is fourth. After "gol", only "golf" matches.
Constraints
1 <= words.length <= 10^41 <= words[i].length <= 201 <= typed.length <= 30words[i]andtypedcontain only lowercase English letters.- All words in
wordsare distinct.