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.

Examples

Example 1:

1
2
3
4

Input: numbers = ["1","2","4","3"]
Output: true
Explanation:
No number is a prefix of another number, so the output is true.

Example 2:

1
2
3
4

Input: numbers = ["001","007","15","00153"]
Output: false
Explanation:
The string "001" is a prefix of the string "00153". Thus, the output is false.

Solution

Method 1 – Sort and Check Prefix

Intuition

If any phone number is a prefix of another, the answer is false. We can sort the phone numbers and check if any number is a prefix of the next one in the sorted list.

Approach

Sort the phone numbers. For each consecutive pair, check if the first is a prefix of the second. If so, return false. Otherwise, return true.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
    bool isPrefixFree(vector<string>& numbers) {
        sort(numbers.begin(), numbers.end());
        for (int i = 0; i + 1 < numbers.size(); ++i) {
            if (numbers[i+1].find(numbers[i]) == 0)
                return false;
        }
        return true;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import "sort"
func isPrefixFree(numbers []string) bool {
    sort.Strings(numbers)
    for i := 0; i+1 < len(numbers); i++ {
        if len(numbers[i+1]) > len(numbers[i]) && numbers[i+1][:len(numbers[i])] == numbers[i] {
            return false
        }
    }
    return true
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import java.util.*;
class Solution {
    public boolean isPrefixFree(String[] numbers) {
        Arrays.sort(numbers);
        for (int i = 0; i + 1 < numbers.length; i++) {
            if (numbers[i+1].startsWith(numbers[i]))
                return false;
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun isPrefixFree(numbers: Array<String>): Boolean {
        numbers.sort()
        for (i in 0 until numbers.size - 1) {
            if (numbers[i+1].startsWith(numbers[i])) return false
        }
        return true
    }
}
1
2
3
4
5
6

def isPrefixFree(numbers: list[str]) -> bool:
    numbers.sort()
    for a, b in zip(numbers, numbers[1:]):
        if b.startswith(a):
            return False
    return True
1
2
3
4
5
6
7
8
9

pub fn is_prefix_free(mut phone_numbers: Vec<String>) -> bool {
    phone_numbers.sort();
    for i in 0..phone_numbers.len()-1 {
        if phone_numbers[i+1].starts_with(&phone_numbers[i]) {
            return false;
        }
    }
    true
}
1
2
3
4
5
6
7

function isPrefixFree(numbers: string[]): boolean {
    numbers.sort();
    for (let i = 0; i + 1 < numbers.length; i++) {
        if (numbers[i+1].startsWith(numbers[i])) return false;
    }
    return true;
}

Complexity

  • ⏰ Time complexity: O(n log n + nL), where n is the number of phone numbers and L is the average length.
  • 🧺 Space complexity: O(1) (ignoring sort space).