Phone Number Prefix - Practice Coding Problems

Phone Number Prefix - Problem

You are given a string array numbers that represents phone numbers. Return true if no phone number is a prefix of any other phone number; otherwise, return false.

A prefix is a substring that appears at the beginning of another string. For example, "123" is a prefix of "12345", but "234" is not a prefix of "12345".

Input & Output

Example 1 — Has Prefix

$ Input: numbers = ["123", "12", "456"]

› Output: false

💡 Note: "12" is a prefix of "123", so return false

Example 2 — No Prefix

$ Input: numbers = ["123", "456", "789"]

› Output: true

💡 Note: No number is a prefix of any other number

Example 3 — Single Digit Prefix

$ Input: numbers = ["1", "12", "123"]

› Output: false

💡 Note: "1" is a prefix of both "12" and "123"

Constraints

1 ≤ numbers.length ≤ 1000
1 ≤ numbers[i].length ≤ 20
numbers[i] consists of digits only

Visualization

Tap to expand

Understanding the Visualization

Input

Array of phone number strings

Process

Check if any number is prefix of another

Output

Return true if no prefix exists, false otherwise

Key Takeaway

🎯 Key Insight: Sort the array first - prefixes will always be adjacent to their longer versions

Asked in

G Google 45 a Amazon 38 M Microsoft 32

The key insight is that after sorting the phone numbers lexicographically, any prefix relationship can only exist between adjacent elements. Best approach is sort first then check adjacent pairs. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Comparison	O(n² × m)	O(1)	Compare every phone number with every other number
Sort Then Check Adjacent	O(n log n + n × m)	O(1)	Sort array then only check adjacent pairs for prefix relationship

Brute Force Comparison — Algorithm Steps

Iterate through each phone number
For each number, check against all other numbers
Return false if any number is a prefix of another

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare First

Check if first number is prefix of others

Compare Second

Check if second number is prefix of others

Result

Return false if any prefix found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(char numbers[][20], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && strstr(numbers[j], numbers[i]) == numbers[j]) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char numbers[100][20];
    int count = 0;
    char *token = strtok(line, "[],\"");
    while (token != NULL) {
        if (strlen(token) > 0 && strcmp(token, " ") != 0) {
            strcpy(numbers[count], token);
            count++;
        }
        token = strtok(NULL, "[],\"");
    }
    
    bool result = solution(numbers, count);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × m)

n² comparisons between all pairs, each comparison takes O(m) where m is average string length

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

23.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler