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.
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.
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.
Bash
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.
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.
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.
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.
Shell
| 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. |
| awk | — |
| 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 |
LeetCode Valid Phone Numbers Solution Explained - Java • Nick White • 7,684 views views
Watch 7 more video solutions →Practice Valid Phone Numbers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor