Medium · System Design

Dictionary and spell

Given an initial list of lowercase words and a sequence of addWord(word), search(word) and suggest(prefix, limit) calls, return in order the result of every search (whether that exact word has been added) and every suggest (the lexicographically smallest limit added words that start with prefix, in lexicographic order, or all of them if there are fewer).

Examples

Example 1

{
  "words": ["cat", "cats", "car", "card"],
  "ops": [
    {"kind": "search", "word": "cat"},
    {"kind": "search", "word": "ca"},
    {"kind": "suggest", "prefix": "ca", "limit": 3}
  ]
}

Output: [ true, false, ["car", "card", "cat"] ]

Example 2

{
  "words": ["cat", "car"],
  "ops": [
    {"kind": "suggest", "prefix": "ca", "limit": 2}
  ]
}

Output: [ ["car", "cat"] ]

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.