193. Valid Phone Numbers - Solution & Code

The problem

Given a text file file.txt that contains a list of phone numbers (one per line), write a one-liner bash script to print all valid phone numbers.

You may assume that a valid phone number must appear in one of the following two formats: (xxx) xxx-xxxx or xxx-xxx-xxxx. (x means a digit)

You may also assume each line in the text file must not contain leading or trailing white spaces.

Example:

Assume that file.txt has the following content:

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

Your script should output the following valid phone numbers:

987-123-4567
(123) 456-7890

Approach overview

Problem Overview: Given a text file file.txt containing one phone number per line, output only the lines that represent valid US phone numbers. A number is valid if it matches either xxx-xxx-xxxx or (xxx) xxx-xxxx, where each x is a digit. The task is primarily about precise pattern validation using shell tools.

Approach 1: Regular Expression Matching with Shell Utilities (O(n) time, O(1) space)

The most direct solution uses regular expressions with tools like grep, sed, or awk. You define a regex pattern that strictly matches the two allowed formats: ^([0-9]{3}-[0-9]{3}-[0-9]{4}|$[0-9]{3}$ [0-9]{3}-[0-9]{4})$. The anchors ^ and $ ensure the entire line matches the format, preventing partial matches. The command scans each line of the file and prints only those matching the pattern. Since every line is checked once, the time complexity is O(n) where n is the number of lines, and space usage remains O(1) because processing is streaming-based.

Approach 2: String Parsing and Manual Validation (O(n) time, O(1) space)

This approach iterates through each line and validates characters manually using string operations. You check line length, verify digit positions, and confirm separators such as -, parentheses, and spaces appear at the correct indices. For example, the xxx-xxx-xxxx format must have hyphens at positions 3 and 7, while (xxx) xxx-xxxx requires parentheses and a space in fixed positions. Each character check is constant time, so scanning all lines still runs in O(n) time with O(1) extra space. This approach appears in implementations using languages like Python, Java, or C++ where explicit validation replaces regex.

Approach 3: Regex Validation in General-Purpose Languages (O(n) time, O(1) space)

Another option is compiling the same regex pattern inside languages such as Python, Java, C++, or JavaScript. Each line from the file is read and matched against the compiled expression. Regex engines efficiently validate the structure without manual index checks. This method is common in problems tagged under strings and shell, especially when file input or pattern filtering is required.

Recommended for interviews: The regex-based shell solution is the expected answer because the problem is designed to test familiarity with command-line pattern matching. A manual parsing approach demonstrates understanding of string validation and is useful when regex is unavailable. In practice, regex is preferred because it expresses the constraints clearly and keeps the implementation concise.

Approach 1: Regular Expression Matching

Use regular expressions to match lines in the text file that conform to the specified valid phone number formats. Regular expressions are powerful tools for string pattern matching and can be used efficiently in bash scripts for this purpose.

Bash

grep -E '^\(\d{3}\) \d{3}-\d{4}$|^\d{3}-\d{3}-\d{4}$' file.txt

This one-liner uses the grep command with the -E option to enable extended regex. It matches lines that satisfy either of the two valid phone number formats: "(xxx) xxx-xxxx" or "xxx-xxx-xxxx" where x is a digit. The ^ and $ are used to ensure that the entire line matches this pattern, with no extra characters.

Complexity

The time complexity is O(n), where n is the number of lines in the file, as the regex needs to scan each line once. The space complexity is O(1), since it operates directly on the input without using extra storage.

Try this approach in the editor

Approach 2: Primary Matching Techniques in Multiple Languages

In addition to bash, solve the problem using common programming languages that can process file I/O and regex pattern matching. This involves reading the file line by line and applying regex to check and print valid phone numbers.

Python

import re
with open('file.txt', 'r') as file:
    for line in file:
        if re.match(r'^(\(\d{3}\) \d{3}-\d{4})|(\d{3}-\d{3}-\d{4})$', line):
            print(line, end='')

Java

import java.io.*;
import java.util.regex.*;
public class ValidPhoneNumbers {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader("file.txt"));
        String line;
        Pattern pattern = Pattern.compile("^(\\([0-9]{3}\\) [0-9]{3}-[0-9]{4})|[0-9]{3}-[0-9]{3}-[0-9]{4}$");
        while ((line = reader.readLine()) != null) {
            Matcher matcher = pattern.matcher(line);
            if (matcher.matches()) {
                System.out.println(line);
            }
        }
        reader.close();
    }
}

C++

#include <iostream>
#include <fstream>
#include <regex>
using namespace std;
int main() {
    ifstream file("file.txt");
    string line;
    regex pattern("^(\([0-9]{3}\) [0-9]{3}-[0-9]{4})|[0-9]{3}-[0-9]{3}-[0-9]{4}$");
    while (getline(file, line)) {
        if (regex_match(line, pattern)) {
            cout << line << endl;
        }
    }
    file.close();
    return 0;
}

JavaScript

const fs = require('fs');
const data = fs.readFileSync('file.txt', 'utf8');
const lines = data.split('\n');
const pattern = /^(\([0-9]{3}\) [0-9]{3}-[0-9]{4})|[0-9]{3}-[0-9]{3}-[0-9]{4}$/;
lines.forEach(line => {
    if (pattern.test(line)) {
        console.log(line);
    }
});

#include <stdio.h>
#include <regex.h>
#define LINE_LENGTH 100
int main() {
    FILE *file = fopen("file.txt", "r");
    if (!file) return 1;
    char line[LINE_LENGTH];
    regex_t regex;
    regcomp(&regex, "^(\([0-9]{3}\) [0-9]{3}-[0-9]{4})|[0-9]{3}-[0-9]{3}-[0-9]{4}$", REG_EXTENDED);
    while (fgets(line, LINE_LENGTH, file)) {
        if (regexec(&regex, line, 0, NULL, 0) == 0) {
            printf("%s", line);
        }
    }
    regfree(&regex);
    fclose(file);
    return 0;
}

using System;
using System.IO;
using System.Text.RegularExpressions;
class Program {
    static void Main() {
        string[] lines = File.ReadAllLines("file.txt");
        string pattern = @"^(\([0-9]{3}\) [0-9]{3}-[0-9]{4})|[0-9]{3}-[0-9]{3}-[0-9]{4}$";
        foreach (string line in lines) {
            if (Regex.IsMatch(line, pattern)) {
                Console.WriteLine(line);
            }
        }
    }
}

In this solution, the file is opened and read line by line. The re.match function checks if each line matches either of the valid phone number formats. If it matches, the line is printed.

Complexity

Time complexity is O(n) due to scanning each line once. Space complexity is O(1) since only individual lines are stored temporarily during processing.

Try this approach in the editor

Complexity comparison

Approach	Complexity
Regular Expression Matching	The time complexity is O(n), where n is the number of lines in the file, as the regex needs to scan each line once. The space complexity is O(1), since it operates directly on the input without using extra storage.
Primary Matching Techniques in Multiple Languages	Time complexity is O(n) due to scanning each line once. Space complexity is O(1) since only individual lines are stored temporarily during processing.

Complexity analysis

Approach	Time	Space	When to Use
Regex Matching with grep/sed/awk	O(n)	O(1)	Best for shell-based solutions and command-line text filtering
Manual String Validation	O(n)	O(1)	Useful when regex is unavailable or when implementing in low-level languages
Regex in General-Purpose Languages	O(n)	O(1)	When processing files in Python, Java, C++, or JavaScript applications

Frequently asked questions

Is Valid Phone Numbers easy or hard?

The problem is classified as Easy because it focuses on correct pattern matching rather than algorithmic complexity. Understanding regex anchors, digit groups, and exact formatting is the main challenge.

Valid Phone Numbers Python/Java solution

In Python or Java, read each line and apply a compiled regex pattern like ^([0-9]{3}-[0-9]{3}-[0-9]{4}|$[0-9]{3}$ [0-9]{3}-[0-9]{4})$. If the line matches, print or store it. This approach maintains O(n) time complexity with constant extra memory.

How to solve Valid Phone Numbers in O(n)?

Read the file line by line and validate each line using a regex pattern that matches the two allowed formats. Anchors (^ and $) ensure the entire line follows the structure. Tools like grep or awk apply the pattern to every line, producing an O(n) scan of the file.

What is the best approach for Valid Phone Numbers?

Regular expression matching using shell utilities like grep is the most efficient and concise approach. A single regex can enforce both valid formats: xxx-xxx-xxxx and (xxx) xxx-xxxx. The solution scans each line once, resulting in O(n) time complexity with constant extra space.

Is Valid Phone Numbers asked at Google/Amazon/Meta?

The problem focuses on regex and shell command skills rather than complex algorithms. Variants of pattern validation and text filtering appear in system scripting interviews and DevOps-style assessments at large companies, including teams within Google and Amazon that evaluate command-line proficiency.

What data structure is used in Valid Phone Numbers?

No complex data structure is required. The problem relies on pattern matching and sequential file processing. Implementations typically use regular expressions or simple string checks while reading lines from the file.

What is the time complexity of Valid Phone Numbers?

The time complexity is O(n), where n is the number of lines in the input file. Each line is checked once against a regex pattern or a set of character validation rules. Space complexity remains O(1) because the solution processes lines sequentially without storing additional data structures.

Valid Phone Numbers solution and explanation

The problem

Approach overview

Approach 1: Regular Expression Matching

Approach 2: Primary Matching Techniques in Multiple Languages

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Valid Phone Numbers solution and explanation

The problem

Approach overview

Approach 1: Regular Expression Matching

Approach 2: Primary Matching Techniques in Multiple Languages

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems