LeetCode 193 - Valid Phone Numbers

Difficulty: 🟢 Easy
Topics: Shell

Solution

Problem Understanding

This problem asks us to process a text file named file.txt and print only the phone numbers that match one of two valid formats.

The valid formats are:

xxx-xxx-xxxx

and

(xxx) xxx-xxxx

In both formats, every x represents a single digit from 0 to 9.

The task is not to transform the input or extract partial matches. Instead, we must validate entire lines. A line should only be printed if the whole line exactly matches one of the required phone number patterns.

The input is a plain text file where each line contains one string. Some lines may contain valid phone numbers, while others may contain invalid formats. The output should consist only of the valid lines, printed exactly as they appear.

A very important detail is that the problem guarantees there are no leading or trailing spaces on any line. This simplifies validation because we do not need to trim whitespace before checking formats.

The core challenge is recognizing structured text patterns efficiently. Since this is a Shell problem, the intended solution uses regular expressions together with standard Unix text processing tools such as grep, awk, or sed.

Several edge cases are important:

A line with extra characters before or after a valid pattern must be rejected.
A line with incorrect spacing must be rejected.
A line with missing parentheses or misplaced hyphens must be rejected.
A line containing letters instead of digits must be rejected.
A line that partially matches a valid format should not be printed.

For example:

123-456-7890abc

is invalid because the line contains extra characters after the phone number.

Similarly:

(123)-456-7890

is invalid because the required space after the closing parenthesis is missing.

Approaches

Brute Force Approach

A brute force solution would manually parse every line character by character and verify whether it matches one of the two allowed formats.

For example, for the format xxx-xxx-xxxx, we could:

Check that the string length is exactly 12
Verify that characters at positions 3 and 7 are hyphens
Verify that all remaining characters are digits

Similarly, for (xxx) xxx-xxxx, we could:

Check that the string length is exactly 14
Verify the exact placement of parentheses, spaces, and hyphens
Verify that all digit positions contain numbers

This approach works because the formats are fixed and small. Every line can be validated deterministically.

However, this method is verbose and error prone. Manual character checking becomes tedious, especially when text pattern matching is exactly what regular expressions are designed for.

Optimal Approach

The better solution is to use a regular expression.

A regular expression allows us to describe both valid formats compactly and accurately. Since the problem is fundamentally pattern matching, regex is the natural tool.

The key insight is that both valid formats are fixed templates:

xxx-xxx-xxxx
(xxx) xxx-xxxx

We can encode these directly in a regex:

^(\([0-9]{3}\) [0-9]{3}-[0-9]{4}|[0-9]{3}-[0-9]{3}-[0-9]{4})$

This expression ensures:

^ marks the beginning of the line
$ marks the end of the line
[0-9]{3} means exactly three digits
[0-9]{4} means exactly four digits
$ and $ match literal parentheses
The | operator allows either valid format

Using grep with this regex gives a concise and efficient one line solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(1)	Manually checks every character in every line
Optimal	O(n × m)	O(1)	Uses regex pattern matching with grep

Here:

n is the number of lines
m is the maximum line length

Algorithm Walkthrough

Read the input file line by line. Each line represents one possible phone number candidate.
For every line, compare it against a regular expression pattern that describes the two valid phone number formats.
Use the beginning of line anchor ^ to ensure matching starts at the first character.
Use the end of line anchor $ to ensure matching ends at the last character. This prevents partial matches.
Define the first valid format:

[0-9]{3}-[0-9]{3}-[0-9]{4}

This matches three digits, a hyphen, three digits, another hyphen, and four digits. 6. Define the second valid format:

\([0-9]{3}\) [0-9]{3}-[0-9]{4}

This matches:

An opening parenthesis
Three digits
A closing parenthesis
One space
Three digits
A hyphen
Four digits

Combine both formats using the alternation operator |.
Print only the lines that fully match the pattern.

Python Solution

Even though this is a Shell problem, below is an equivalent Python implementation that validates phone numbers using regular expressions.

import re
from typing import List

class Solution:
    def validPhoneNumbers(self, phone_numbers: List[str]) -> List[str]:
        pattern = re.compile(
            r"^(\(\d{3}\) \d{3}-\d{4}|\d{3}-\d{3}-\d{4})$"
        )

        valid_numbers = []

        for number in phone_numbers:
            if pattern.match(number):
                valid_numbers.append(number)

        return valid_numbers

The implementation begins by compiling a regular expression pattern. Compiling the regex once is more efficient than recreating it repeatedly for every line.

The pattern contains two alternatives:

$\d{3}$ \d{3}-\d{4}
\d{3}-\d{3}-\d{4}

The anchors ^ and $ guarantee that the entire string must match exactly.

The algorithm then iterates through every phone number. If the regex matches, the number is appended to the result list.

Finally, the list of valid phone numbers is returned.

For the actual LeetCode Shell submission, the intended one liner is:

grep -E '^(\([0-9]{3}\) [0-9]{3}-[0-9]{4}|[0-9]{3}-[0-9]{3}-[0-9]{4})$' file.txt

Go Solution

package main

import (
	"regexp"
)

type Solution struct{}

func (s Solution) ValidPhoneNumbers(phoneNumbers []string) []string {
	pattern := regexp.MustCompile(`^(\([0-9]{3}\) [0-9]{3}-[0-9]{4}|[0-9]{3}-[0-9]{3}-[0-9]{4})$`)

	var validNumbers []string

	for _, number := range phoneNumbers {
		if pattern.MatchString(number) {
			validNumbers = append(validNumbers, number)
		}
	}

	return validNumbers
}

The Go solution closely mirrors the Python version. The regexp package provides regex support through MustCompile.

Go slices are used to store valid phone numbers dynamically. Unlike Python lists, slices require explicit append operations through the built in append function.

There are no integer overflow concerns in this problem because we are only processing strings.

Worked Examples

Example 1

Input:

987-123-4567
123 456 7890
(123) 456-7890

Regex pattern:

^(\([0-9]{3}\) [0-9]{3}-[0-9]{4}|[0-9]{3}-[0-9]{3}-[0-9]{4})$

Line	Matches First Format	Matches Second Format	Valid
`987-123-4567`	Yes	No	Yes
`123 456 7890`	No	No	No
`(123) 456-7890`	No	Yes	Yes

Output:

987-123-4567
(123) 456-7890

Detailed Trace

Line 1: `987-123-4567`

The regex checks:

Three digits: 987
Hyphen: -
Three digits: 123
Hyphen: -
Four digits: 4567

The entire string matches exactly, so it is printed.

Line 2: `123 456 7890`

The regex expects either hyphens or parentheses in specific positions.

This string contains spaces instead of hyphens, so the match fails.

The line is skipped.

Line 3: `(123) 456-7890`

The regex checks:

Opening parenthesis: (
Three digits: 123
Closing parenthesis: )
Space:
Three digits: 456
Hyphen: -
Four digits: 7890

The full pattern matches successfully, so the line is printed.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × m)	Each line is scanned against the regex
Space	O(1)	Only constant extra memory is used

The regex engine processes each line independently. Since every character may need to be inspected during matching, the runtime is proportional to the total input size.

The space usage remains constant because we only store the regex pattern and a few temporary variables.

Edge Cases

Lines With Extra Characters

A common mistake is allowing partial matches.

For example:

123-456-7890abc

A naive regex without ^ and $ might incorrectly accept this line because the valid phone number appears at the beginning.

The implementation prevents this by anchoring the regex to the start and end of the line.

Incorrect Parentheses Placement

Consider:

(123)-456-7890

This is invalid because the required format demands a space after the closing parenthesis.

The regex explicitly enforces:

\([0-9]{3}\)

which includes the space character.

Non Digit Characters

A line such as:

abc-def-ghij

must be rejected.

The regex uses [0-9] or \d to require digits in every numeric position, ensuring alphabetic characters never match.

Missing Digits

An input like:

123-45-6789

contains only two digits in the middle group.

The quantifier {3} enforces exactly three digits, so the line is rejected automatically.

Empty Lines

An empty line should not be considered valid.

Because the regex requires the full structure of a phone number, empty strings fail immediately and are ignored correctly.