We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Phone Number Prefix

Number: 3836

Difficulty: Easy

Paid? Yes

Companies: N/A

Problem Description

Given a list of phone numbers (represented as strings), determine if no phone number is a prefix of any other phone number. If any number is found to be a prefix of another, return false; otherwise, return true.

Key Insights

  • Sorting the list of phone numbers lexicographically ensures that if a number is a prefix of another, they will appear consecutively.
  • Once the list is sorted, only adjacent pairs need to be compared.
  • Alternatively, a Trie data structure could be used to detect prefix relationships during insertions.
  • Given the moderate input size, the sorting approach is efficient and simple to implement.

Space and Time Complexity

Time Complexity: O(n log n * m) where n is the number of phone numbers and m is the average length of a phone number. Space Complexity: O(n * m) in the worst case for the sorting method; using a Trie may have similar space requirements.

Solution

The solution involves sorting the list of phone numbers. After sorting, every number is only compared with the next number in the list. If the current number is a prefix of the next, the function returns false immediately. If no prefix condition is found throughout the list, the function returns true. This method leverages the fact that prefixes will be adjacent in the sorted order, thereby reducing the number of necessary comparisons.

Code Solutions

# Function to check for phone number prefixes
def is_prefix(numbers):
    # Sort the phone numbers lexicographically
    numbers.sort()
    # Iterate through consecutive pairs
    for i in range(len(numbers) - 1):
        # If the next number starts with the current number, a prefix is found
        if numbers[i+1].startswith(numbers[i]):
            return False
    return True

# Example usage:
numbers = ["001", "007", "15", "00153"]
print(is_prefix(numbers))  # Expected output: False
← Back to All Questions