193. Valid Phone Numbers - Detailed Explanation
Problem Statement
You are given a table called PhoneNumbers that contains a column phone. The task is to write a SQL query to find all valid phone numbers from the table. A valid phone number is defined as a string that consists of exactly 10 digits (0-9) with no additional characters, spaces, or symbols.
Example
Suppose the PhoneNumbers table contains the following data:
phone |
---|
1234567890 |
123-456-7890 |
0123456789 |
123456789 |
(123)4567890 |
-
Valid Phone Numbers:
- "1234567890" → Exactly 10 digits.
- "0123456789" → Exactly 10 digits (leading zero is acceptable).
-
Invalid Phone Numbers:
- "123-456-7890" → Contains dashes.
- "123456789" → Only 9 digits.
- "(123)4567890" → Contains parentheses.
The expected output should include only the rows with valid phone numbers, i.e., "1234567890" and "0123456789".
Hints
-
Use Regular Expressions:
The SQL dialect (MySQL in this case) provides a REGEXP operator that can be used to match patterns. -
Exact Match Pattern:
Create a pattern that ensures the entire string contains exactly 10 digits. Use the caret^
to indicate the start of the string and the dollar sign$
to indicate the end. The pattern should look like^[0-9]{10}$
.
Approach Overview
Using Regular Expression Matching
- Step 1:
Select the phone column from the PhoneNumbers table. - Step 2:
Use theWHERE
clause with theREGEXP
operator to filter rows. The regular expression'^[0-9]{10}$'
ensures that:^
marks the beginning of the string.[0-9]{10}
matches exactly 10 digits.$
marks the end of the string.
- Step 3:
Return the filtered rows that match the valid phone number format.
SQL Query
SELECT phone FROM PhoneNumbers WHERE phone REGEXP '^[0-9]{10}$';
Detailed Step-by-Step Explanation
-
Select the Column:
- We begin with
SELECT phone FROM PhoneNumbers
to retrieve all phone numbers from the table.
- We begin with
-
Apply the Regular Expression Filter:
- The condition
phone REGEXP '^[0-9]{10}$'
is applied in theWHERE
clause. - Pattern Breakdown:
^
: Ensures that the match starts at the beginning of the string.[0-9]{10}
: Matches exactly 10 digits (each digit between 0 and 9).$
: Ensures that the match ends at the end of the string.
- This pattern guarantees that only strings with exactly 10 digits, and no other characters, are selected.
- The condition
-
Return Valid Results:
- The query returns only those rows where the phone value is a valid 10-digit number.
Python Code
Python Explanation
-
Regular Expression Setup:
We compile the regex pattern^[0-9]{10}$
which:- Uses
^
and$
to anchor the pattern to the beginning and end of the string. - Uses
[0-9]{10}
to ensure exactly 10 digits are matched.
- Uses
-
Filtering:
A list comprehension checks each phone number against the regex pattern. Only numbers that match are kept. -
Example Usage:
A sample list of phone numbers is provided, and the valid ones are printed.
Java Code
Java Explanation
-
Regular Expression Setup:
APattern
object is created using"^[0-9]{10}$"
to ensure that the string contains exactly 10 digits. -
Filtering:
We loop through the list of phone numbers and usematcher(phone).matches()
to test each string. Valid phone numbers are added to the resulting list. -
Main Method:
Themain
method provides an example list of phone numbers and prints the valid ones.
Complexity Analysis
Python Code
-
Time Complexity:
- Let n be the number of phone numbers in the input list.
- The code iterates through each phone number once using a list comprehension.
- For each phone number, the regex pattern
^[0-9]{10}$
is applied. Since each phone number is of fixed length (10 characters), the regex match operation takes O(1) time. - Overall Time Complexity: O(n).
-
Space Complexity:
- The output list stores up to n phone numbers in the worst-case scenario (if all numbers are valid).
- The compiled regex pattern and temporary variables use constant space.
- Overall Space Complexity: O(n).
Java Code
-
Time Complexity:
- Let n be the number of phone numbers in the input list.
- The code iterates through each phone number in a for loop, performing a regex match on each.
- Since each phone number is of fixed length (10 characters), the regex match operation takes O(1) time.
- Overall Time Complexity: O(n).
-
Space Complexity:
- An
ArrayList
is used to store the valid phone numbers. In the worst case, if all phone numbers are valid, the list will contain n elements. - The compiled regex pattern occupies constant space.
- Overall Space Complexity: O(n).
- An
Both implementations efficiently check each phone number with constant-time regex operations, leading to linear time complexity with respect to the number of phone numbers, and require linear space to store the results in the worst case.
Common Mistakes
-
Missing Anchors:
Omitting^
and$
may allow strings that have extra characters before or after the 10 digits. -
Incorrect Quantifier:
Using a quantifier like*
(zero or more) or+
(one or more) instead of{10}
might match strings with the wrong number of digits. -
Ignoring Non-Digit Characters:
Not enforcing that each character must be a digit (e.g., allowing dashes, spaces, or parentheses) will result in invalid phone numbers being accepted.
Edge Cases
- Leading Zeros:
Phone numbers like "0123456789" are valid. - Extra Characters:
Any string with more or fewer than 10 digits, or containing any non-digit character, must be excluded.
Related Practice Problems
-
Regular Expression Matching (LeetCode 10): This problem focuses on implementing regular expression matching with support for '.' and '*' operators. It deepens your understanding of regex patterns and dynamic programming.
-
17. Letter Combinations of a Phone Number: This problem covers how to generate all possible letter combinations that the number could represent based on the telephone keypad mapping given a string of digits (from 2 to 9).
GET YOUR FREE
Coding Questions Catalog
