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
Is UML a design pattern?
Faang-Level System Design Interview Questions and Solutions
Master FAANG system design interviews with top questions, expert solutions, and best practices. Learn proven strategies, avoid common pitfalls, and ace your interview!
What is Rate Limiting?
Related Courses
Image
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.
Image
Grokking Modern AI Fundamentals
Master the fundamentals of AI today to lead the tech revolution of tomorrow.
Image
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.
;