Watch 10 video solutions for Valid Phone Numbers, a easy level problem involving Shell. This walkthrough by CrioDo has 304,593 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
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 | 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 |
