A router's console lets operators type any prefix of a command as long as it's unambiguous: conf for configure, sh for show. Build the lookup.
Implement class CommandSet:
CommandSet(commands: list[str]): the known commands (distinct, lowercase letters, length >= 1). The list may be empty.resolve(typed: str) -> str | None, for a non-empty lowercasetyped:- If
typedis exactly a command, return it (even if longer commands also start with it). - Otherwise, if exactly one command starts with
typed, return that command. - Otherwise (no command starts with it, or several do) return
None.
- If
cs = CommandSet(["show", "shutdown", "set", "configure", "copy"])
cs.resolve("sh") # None ("show" and "shutdown": ambiguous)
cs.resolve("shu") # "shutdown"
cs.resolve("conf") # "configure"
cs.resolve("set") # "set" (exact match)
cs.resolve("c") # None ("configure" and "copy")
cs.resolve("reload") # None
The tests build a set of 20,000 commands and resolve 20,000 inputs, so checking startswith against every command is too slow. resolve must cost O(len(typed)).
Show hint
Build a trie. Besides its children, let each node remember how many commands pass through it, whether a command ends there, and one command that passes through it. Then resolve is a single walk down the trie.