LeetCode 3491 - Phone Number Prefix

The problem is asking us to determine whether any phone number in a given list is a prefix of another phone number. In simpler terms, if you have a list of strings representing numbers, you need to check that no string starts with another string from the list.

leetcodeeasyarraystringtriesorting

LeetCode Problem 3491

Difficulty: 🟢 Easy
Topics: Array, String, Trie, Sorting

Solution

Problem Understanding

The problem is asking us to determine whether any phone number in a given list is a prefix of another phone number. In simpler terms, if you have a list of strings representing numbers, you need to check that no string starts with another string from the list. If all numbers are independent prefixes, the output should be true; if even one number is a prefix of another, the output should be false.

The input numbers is an array of strings, each containing only digits from '0' to '9'. The expected output is a boolean indicating whether the prefix condition is satisfied. The constraints are small: the length of the array is between 2 and 50, and each number string is between 1 and 50 characters. This means performance does not need to scale to thousands of elements, but our solution should still avoid unnecessary work.

Important edge cases include situations where one number is entirely contained at the start of another, for example ["001", "00153"], and when all numbers have completely distinct digits, e.g., ["1","2","3"]. The problem guarantees that the input contains only digits, so we do not need to handle non-numeric strings.

Approaches

The brute-force approach involves comparing every number with every other number. For each pair, we check if one string is a prefix of the other. While this guarantees correctness, it is inefficient because for n numbers, we make n*(n-1)/2 comparisons, each potentially checking up to 50 characters. This results in a worst-case time complexity of O(n² * k), where k is the average length of a number.

A more optimal approach leverages sorting. If we sort the numbers lexicographically, any potential prefix relationship will appear between consecutive elements only. This is because prefixes naturally group together in sorted order. After sorting, we only need to compare each number with the next one, drastically reducing the number of comparisons to n-1.

Approach Time Complexity Space Complexity Notes
Brute Force O(n² * k) O(1) Compare every pair of numbers for prefix matches
Optimal O(n * k * log n) O(1) Sort numbers and check only consecutive pairs for prefix

Algorithm Walkthrough

  1. Sort the list of phone numbers lexicographically. Sorting groups numbers such that any potential prefix will appear immediately before the number it could prefix.
  2. Iterate through the sorted list from the first number to the second-to-last number.
  3. For each number at index i, check if it is a prefix of the number at index i+1. This can be done by checking if the next number starts with the current number.
  4. If any prefix is detected, return false immediately.
  5. If the loop completes without detecting any prefix, return true.

Why it works: Sorting ensures that all numbers that could possibly be a prefix of another number appear consecutively. By checking only consecutive numbers, we ensure we catch all prefix relationships without redundant comparisons. This maintains correctness while reducing computational work.

Python Solution

from typing import List

class Solution:
    def phonePrefix(self, numbers: List[str]) -> bool:
        numbers.sort()
        for i in range(len(numbers) - 1):
            if numbers[i+1].startswith(numbers[i]):
                return False
        return True

In this implementation, we first sort the numbers to bring potential prefixes together. The loop iterates through each number except the last, checking if the following number starts with the current number using the startswith string method. If any prefix relationship is found, the function immediately returns false. If the loop completes, no prefixes exist, so it returns true.

Go Solution

import "sort"
import "strings"

func phonePrefix(numbers []string) bool {
    sort.Strings(numbers)
    for i := 0; i < len(numbers)-1; i++ {
        if strings.HasPrefix(numbers[i+1], numbers[i]) {
            return false
        }
    }
    return true
}

The Go implementation mirrors the Python logic. We use sort.Strings to sort the slice of numbers lexicographically and strings.HasPrefix to check for prefix relationships. The loop iterates from 0 to len(numbers)-2 to compare each number with the next. Return values follow the same logic as in Python.

Worked Examples

Example 1: numbers = ["1","2","4","3"]

Sorted: ["1","2","3","4"]

i numbers[i] numbers[i+1] startswith?
0 "1" "2" false
1 "2" "3" false
2 "3" "4" false

No prefixes found → return true.

Example 2: numbers = ["001","007","15","00153"]

Sorted: ["001","00153","007","15"]

i numbers[i] numbers[i+1] startswith?
0 "001" "00153" true

Prefix detected → return false.

Complexity Analysis

Measure Complexity Explanation
Time O(n * k * log n) Sorting takes O(n log n), comparing consecutive numbers is O(n * k) in total
Space O(1) Sorting can be done in-place, no extra data structures required

The time complexity is dominated by the sort operation. Checking prefixes only requires a linear scan over the sorted list. Space complexity is minimal because we do not create additional data structures aside from the input list.

Test Cases

# provided examples
assert Solution().phonePrefix(["1","2","4","3"]) == True  # no prefixes
assert Solution().phonePrefix(["001","007","15","00153"]) == False  # "001" is prefix of "00153"

# edge and boundary cases
assert Solution().phonePrefix(["12", "123", "1234"]) == False  # multiple nested prefixes
assert Solution().phonePrefix(["9", "8", "7", "6"]) == True  # all distinct
assert Solution().phonePrefix(["0", "00"]) == False  # prefix with single digit
assert Solution().phonePrefix(["12345678901234567890", "1234567890123456789"]) == False  # long numbers, prefix
assert Solution().phonePrefix(["5","55","555"]) == False  # repeated digit patterns
assert Solution().phonePrefix(["101","202","303","404"]) == True  # same length, no prefix
Test Why
["1","2","4","3"] Simple case, no prefixes
["001","007","15","00153"] Detect prefix at start
["12", "123", "1234"] Nested prefixes, longer chain
["9","8","7","6"] All numbers distinct, no prefixes
["0","00"] Edge with single-character number
["12345678901234567890","1234567890123456789"] Very long numbers with prefix
["5","55","555"] Repeated patterns of digits
["101","202","303","404"] Same length numbers, no prefix

Edge Cases

One important edge case is when a single-digit number is a prefix of a longer number. For instance, ["0","00"] must correctly return false because the first number matches the start of the second. A naive implementation might ignore single-character strings, but sorting and startswith ensures correctness.

Another edge case is nested prefixes, where multiple numbers form a chain, like ["12","123","1234"]. The algorithm correctly detects the first prefix and stops, avoiding unnecessary checks of subsequent numbers.

Finally, long numbers close to the maximum length, such as ["12345678901234567890","1234567890123456789"], test the string comparison logic for correctness. Sorting and startswith handle arbitrary string lengths efficiently within the given constraints. The problem provides numbers are completely unrelated.