League Radio Code Check
Check that no string in a list is a prefix of another
A football league assigns a lowercase letter code to each team's radio channel. A receiver reads a code one letter at a time and switches channels as soon as it recognizes a complete assigned code.
The assignments are safe only if no assigned code is a prefix of another assigned code. A string is a prefix of another string when the second string begins with the entire first string. Identical codes assigned to two different teams also make the assignments unsafe.
Given codes, where each list entry is one team's assigned code, return true if the assignments are safe and false otherwise.
An empty list or a list containing just one code is safe.
Examples
Example 1
Input: codes = ["falcon","otter","raven"] Output: true
The codes begin with different letters, so none is a prefix of another. The assignments are safe.
Example 2
Input: codes = ["redwing","red","blue"] Output: false
The complete code `red` appears at the beginning of `redwing`. The receiver would switch channels before finishing the longer code, so the assignments are unsafe.
Example 3
Input: codes = ["stadium","stadion"] Output: true
Both codes share `stad`, but neither complete code is a prefix of the other. A shared partial prefix is allowed.
Constraints
- 0 <= codes.length <= 2500
- 1 <= codes[i].length <= 30
- Each code contains only lowercase English letters.
- The sum of all code lengths is at most 30000.
Each list entry represents a separate assignment, so duplicate strings are a conflict. The intended solution takes O(S) time and O(S) space, where S is the sum of code lengths.
Hints
Show hint 1Hint 1
Store the codes in a trie, marking nodes where complete codes end.
Show hint 2Hint 2
During insertion, check for a previously completed code along the path. At the final node, also check whether an existing code ends there or continues below it.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return the indices of the first conflicting pair encountered while processing codes from left to right?
- How would you support adding and removing team codes while reporting whether the assignments remain safe?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem