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

Open every published interview problem, solution, scene, and memory room free, with no account.