Problem Description

You are given an array of strings called numbers where each string represents a phone number. Your task is to determine if any phone number in the array is a prefix of another phone number.

A string is considered a prefix of another string if the second string starts with the exact sequence of characters from the first string. For example, "123" is a prefix of "12345", but "124" is not a prefix of "12345".

The function should return true if no phone number is a prefix of any other phone number in the array. It should return false if at least one phone number is a prefix of another.

For example:

• If numbers = ["911", "91125", "222"], the function should return false because "911" is a prefix of "91125"
• If numbers = ["123", "456", "789"], the function should return true because no number is a prefix of any other number

The solution approach sorts the array by string length first, then for each string, checks if any of the shorter strings (that come before it in the sorted array) are prefixes of the current string. This optimization ensures we only check strings that could potentially be prefixes (shorter or equal length strings).

Intuition

The key insight is that if string A is a prefix of string B, then A must be shorter than or equal to B in length. This observation leads us to an important optimization: we only need to check if shorter strings are prefixes of longer strings, never the other way around.

By sorting the array by string length, we create a natural ordering where potential prefixes (shorter strings) come before the strings they might be prefixes of (longer strings). This allows us to process the strings in a specific order and avoid redundant comparisons.

For each string in our sorted array, we only need to look backwards at the strings that came before it (which are guaranteed to be shorter or equal in length). If any of these shorter strings is a prefix of our current string, we've found a prefix relationship and can immediately return false.

The beauty of this approach is its efficiency - we're eliminating impossible prefix relationships from consideration. A string of length 5 can never be a prefix of a string of length 3, so by sorting first, we ensure we never waste time checking such impossible cases.

Additionally, once we find any prefix relationship, we can immediately return false without checking the remaining strings, making the algorithm even more efficient in cases where prefix relationships exist early in our sorted array.

Learn more about Trie and Sorting patterns.

Solution Approach

The implementation follows the sorting and prefix checking strategy outlined in the reference approach:

Step 1: Sort by Length

numbers.sort(key=len)

We sort the numbers array based on the length of each string. This ensures that shorter strings come before longer strings. For example, if we have ["12345", "123", "67"], after sorting it becomes ["67", "123", "12345"].

Step 2: Iterate and Check Prefixes

for i, s in enumerate(numbers):
    if any(s.startswith(t) for t in numbers[:i]):
        return False

For each string s at index i:

• We examine all strings that come before it in the sorted array (numbers[:i])
• These previous strings are guaranteed to be shorter or equal in length to s
• We use Python's startswith() method to check if s begins with any of these shorter strings
• The any() function returns True if at least one string t in numbers[:i] is a prefix of s

Step 3: Return Result

return True

If we've checked all strings and haven't found any prefix relationships, we return True, indicating that no phone number is a prefix of another.

Time Complexity: O(n log n + n²m) where n is the number of strings and m is the average string length. The sorting takes O(n log n), and for each string, we potentially check all previous strings with prefix comparison taking O(m) time.

Space Complexity: O(1) if we don't count the sorting space, or O(n) considering the space used by the sorting algorithm.

Example Walkthrough

Let's walk through the solution with the example numbers = ["911", "91125", "222"].

Step 1: Sort by Length First, we sort the array by string length:

• "911" has length 3
• "222" has length 3
• "91125" has length 5

After sorting: ["911", "222", "91125"]

Step 2: Check Each String for Prefix Relationships

Iteration 1 (i=0, s="911"):

• Check if any string in numbers[:0] (empty list) is a prefix of "911"
• No strings to check, so continue

Iteration 2 (i=1, s="222"):

• Check if any string in numbers[:1] (which is ["911"]) is a prefix of "222"
• Does "222" start with "911"? No
• Continue to next iteration

Iteration 3 (i=2, s="91125"):

• Check if any string in numbers[:2] (which is ["911", "222"]) is a prefix of "91125"
• Does "91125" start with "911"? Yes!
• Since we found a prefix relationship, immediately return False

Result: The function returns False because "911" is a prefix of "91125".

Let's contrast this with an example that returns True: numbers = ["123", "456", "789"]

After sorting by length (all same length, order unchanged): ["123", "456", "789"]

• Check "123": no previous strings to check
• Check "456": does it start with "123"? No
• Check "789": does it start with "123" or "456"? No

Since no prefix relationships were found, the function returns True.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n² × m + n × log n)

The time complexity consists of two main parts:

• Sorting: The sort(key=len) operation takes O(n × log n) time, where n is the number of strings in the array.
• Nested comparison: The outer loop runs n times. For each iteration i, the inner any() function checks up to i strings (from numbers[:i]), and each startswith() comparison takes O(m) time where m is the average length of strings. In the worst case, this results in O(1 + 2 + ... + (n-1)) × O(m) = O(n² × m).
• Combined: O(n × log n + n² × m) = O(n² × m + n × log n) since n² × m dominates when m ≥ 1.

Space Complexity: O(m + log n)

The space complexity comes from:

• The sorting algorithm typically uses O(log n) space for recursive calls in languages like Python (using Timsort).
• The slicing operation numbers[:i] creates a new list, but this is temporary and at most contains O(n) references (not copying the strings themselves).
• The strings themselves require O(m) space for the comparison operations.
• Combined: O(m + log n) where m represents the space needed for string operations and log n for the sorting recursion stack.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Inefficient Repeated Slicing

The current solution uses numbers[:i] inside the loop, which creates a new list slice for each iteration. This adds unnecessary overhead, especially for large arrays.

Problem Code:

for i, current_number in enumerate(numbers):
    if any(current_number.startswith(previous_number) for previous_number in numbers[:i]):
        return False

Better Approach:

for i in range(1, len(numbers)):
    for j in range(i):
        if numbers[i].startswith(numbers[j]):
            return False

Pitfall 2: Missing Edge Case - Duplicate Numbers

If the array contains duplicate phone numbers, they are prefixes of each other by definition. The current solution handles this correctly, but it's worth noting that sorting by length alone doesn't guarantee duplicates will be adjacent.

Example: numbers = ["123", "456", "123"] After sorting by length: ["123", "456", "123"] - duplicates aren't necessarily next to each other.

Enhanced Solution with Early Duplicate Detection:

def phonePrefix(self, numbers: List[str]) -> bool:
    # Check for duplicates first (optional optimization)
    if len(numbers) != len(set(numbers)):
        return False

    numbers.sort(key=len)
    for i in range(1, len(numbers)):
        for j in range(i):
            if numbers[i].startswith(numbers[j]):
                return False
    return True

Pitfall 3: Alternative O(n log n) Solution Using Lexicographic Sorting

The current O(n²) approach can be optimized. When strings are sorted lexicographically, strings with prefix relationships will be adjacent.

More Efficient Solution:

def phonePrefix(self, numbers: List[str]) -> bool:
    # Sort lexicographically instead of by length
    numbers.sort()

    # Only check adjacent pairs
    for i in range(len(numbers) - 1):
        if numbers[i+1].startswith(numbers[i]):
            return False
    return True

This reduces the time complexity from O(n²m) to O(n log n + nm) for the prefix checking phase.