193. Valid Phone Numbers - Detailed Explanation

Free Coding Questions Catalog
Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

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

  1. Use Regular Expressions:
    The SQL dialect (MySQL in this case) provides a REGEXP operator that can be used to match patterns.

  2. 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 the WHERE clause with the REGEXP 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

  1. Select the Column:

    • We begin with SELECT phone FROM PhoneNumbers to retrieve all phone numbers from the table.
  2. Apply the Regular Expression Filter:

    • The condition phone REGEXP '^[0-9]{10}$' is applied in the WHERE 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.
  3. Return Valid Results:

    • The query returns only those rows where the phone value is a valid 10-digit number.

Python Code

Python3
Python3

. . . .

Python Explanation

  1. 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.
  2. Filtering:
    A list comprehension checks each phone number against the regex pattern. Only numbers that match are kept.

  3. Example Usage:
    A sample list of phone numbers is provided, and the valid ones are printed.

Java Code

Java
Java

. . . .

Java Explanation

  1. Regular Expression Setup:
    A Pattern object is created using "^[0-9]{10}$" to ensure that the string contains exactly 10 digits.

  2. Filtering:
    We loop through the list of phone numbers and use matcher(phone).matches() to test each string. Valid phone numbers are added to the resulting list.

  3. Main Method:
    The main 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).

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.
  • 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).

TAGS
leetcode
CONTRIBUTOR
Design Gurus Team
-

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
Related Courses
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the Coding Interview Patterns in Java, Python, JS, C++, C#, and Go. The most comprehensive course with 476 Lessons.
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
Grokking Data Structures & Algorithms for Coding Interviews
Unlock Coding Interview Success: Dive Deep into Data Structures and Algorithms.
Image
One-Stop Portal For Tech Interviews.
Copyright © 2025 Design Gurus, LLC. All rights reserved.
;