Glowing Letter Tiles
In a phone word game, you drag your finger across letter tiles to spell words. While you drag, the trail glows: green if the letters so far already spell a word, amber if they do not yet but could still grow into one, and grey if no word starts that way, so you should let go.
The trail colour updates on every tile you touch, and the dictionary holds tens of thousands of words. The game also adds new words during a season, so the dictionary has to accept additions too.
Your task
Write a class TileDictionary:
constructor(): start with an empty dictionary.add(word): add a word. Adding the same word twice is allowed and changes nothing.isWord(letters): returntrueif exactly this word was added.isPrefix(letters): returntrueif at least one added word starts withletters. A word counts as starting with itself.
Each method should take time proportional to the length of its argument, not to the size of the dictionary.
class TileDictionary
Examples
new TileDictionary()
.add("star")
.add("start")
.isWord("sta")
.isPrefix("sta")
.isWord("start")
.isPrefix("stx")[null, null, null, false, true, true, false]
"sta" is not a word, but both "star" and "start" begin with it: amber. "start" was added: green. No word begins with "stx": grey.
new TileDictionary()
.add("tea")
.isWord("tea")
.isPrefix("tea")
.isWord("te")[null, null, true, true, false]
"tea" is a word, and a word counts as a prefix of itself, so both answers are true. "te" is only the beginning of "tea", so it is not a word.
Constraints
- 1 ≤ length of every word and letters argument ≤ 20
- Only lowercase letters a to z.
- At most 10,000 calls in total.
Start with brute force
Keep every word in a list. For isWord, scan for an equal word; for isPrefix, scan for a word that starts with the letters.
Each query looks at every word, so it costs O(n · L) for n words of length up to L. A hash set fixes isWord, but not isPrefix: a set can only answer "is this exact string here?". You could also put every prefix of every word into a second set, but that stores each word up to 20 times.
Hints
0 of 4 shown- Hint 1
Add "car", "cart" and "cat" on paper. Notice that they share "ca", and two of them share "car". How could you store them so the shared beginnings are written only once?
- Hint 2
Draw a tree where each edge is one letter. Every word is a path from the root, and words with the same beginning share the first part of the path. Checking a prefix is then just following edges letter by letter.
- Hint 3
After "add cart", following c → a → r succeeds, but "car" was never added. Following the path is not enough for
isWord. What extra fact must a node remember? - Hint 4
Make each node a map from letter to child node, plus a flag
endmeaning "a word stops here".addwalks the letters, creating missing children, and setsendon the last node. Both queries walk the letters and return false if a child is missing; thenisPrefixreturns true, andisWordreturns the last node'send.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
A trie (prefix tree) stores words letter by letter, sharing common beginnings. Each node is "the letters so far". Its children are the letters that can come next, and a flag says whether a word ends exactly here.
Trace the first example:
- add "star": create root → s → t → a → r, mark r as an end.
- add "start": s, t, a, r already exist, so just walk them. Create one new child t under r and mark it as an end.
- isWord "sta": walk s → t → a. The node exists but is not an end. False.
- isPrefix "sta": the same walk succeeds. True.
- isWord "start": walk to the second t. It is an end. True.
- isPrefix "stx": after s → t there is no child x. False.
The end flag is the part people forget. Without it, "sta" would count as a word just because "star" passes through it.
class TileDictionary {
constructor() {
this.root = { kids: new Map(), end: false };
}
add(word) {
let node = this.root;
for (const ch of word) {
if (!node.kids.has(ch)) node.kids.set(ch, { kids: new Map(), end: false });
node = node.kids.get(ch);
}
node.end = true; // a word stops here
}
walk(letters) { // node reached by following letters, or null
let node = this.root;
for (const ch of letters) {
node = node.kids.get(ch);
if (!node) return null;
}
return node;
}
isWord(letters) {
const node = this.walk(letters);
return node !== null && node.end;
}
isPrefix(letters) {
return this.walk(letters) !== null;
}
}class TileDictionary:
def __init__(self):
self.root = {"kids": {}, "end": False}
def add(self, word):
node = self.root
for ch in word:
node = node["kids"].setdefault(ch, {"kids": {}, "end": False})
node["end"] = True # a word stops here
def _walk(self, letters): # node reached by following letters, or None
node = self.root
for ch in letters:
node = node["kids"].get(ch)
if node is None:
return None
return node
def is_word(self, letters):
node = self._walk(letters)
return node is not None and node["end"]
def is_prefix(self, letters):
return self._walk(letters) is not NoneRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.