Implementation considerations:
Track current input: accumulate typed characters until '#'
Update on '#': insert the completed sentence into trie, increment frequency
Maintain sorted suggestions: use heap or sorted insertion
Handle special characters: spaces are valid characters in sentences
def input(c):
if c == '#':
self.insert(self.currentInput)
self.currentInput = ""
return []
self.currentInput += c
node = self.findNode(self.currentInput)
if not node:
return []
return [s for s, _ in node.suggestions[:3]]
This problem is complex because it combines trie operations with ranking and stateful input handling.