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 theWHEREclause with theREGEXPoperator 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 PhoneNumbersto 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 theWHEREclause.
- 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: 
 APatternobject 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: 
 Themainmethod 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 ArrayListis 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
$197

$78
$78