Valid Phone Numbers

Easy

#0183Time: O(N * L)Space: O(L)1 company

Companies

Prompt

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

Approaches

4 approaches with complexity analysis and trade-offs.

This approach uses a while loop in bash to read the file line by line. For each line, it uses the [[ ... =~ ... ]] conditional expression to test if the line matches the required regular expression for a valid phone number. If it matches, the line is printed to standard output.

Algorithm

1. Start a while loop to read file.txt line by line into a variable line.
1. For each line, use the [[ ... =~ ... ]] operator to perform a regex match.
1. The regex checks for two patterns separated by | (OR): $[0-9]{3}$ [0-9]{3}-[0-9]{4} or [0-9]{3}-[0-9]{3}-[0-9]{4}.
1. The entire pattern is anchored with ^ and $ to ensure the whole line matches.
1. If the line matches the regex, print the line.
1. Continue until all lines are processed.

Walkthrough

The script reads file.txt line by line using while read -r line. The -r option prevents backslash interpretation. Inside the loop, an if statement checks the line against a regular expression. The regex ^($[0-9]{3}$ [0-9]{3}-[0-9]{4}|[0-9]{3}-[0-9]{3}-[0-9]{4})$ is used to validate the two possible phone number formats. The ^ and $ anchors ensure that the entire line must match one of the formats. If the condition is true, echo "$line" prints the valid phone number. This can be written as a one-liner using the && operator.

1while read -r line; do [[ "$line" =~ ^(\([0-9]{3}\) [0-9]{3}-[0-9]{4}|[0-9]{3}-[0-9]{3}-[0-9]{4})$ ]] && echo "$line"; done < file.txt

Complexity

Time

O(N * L)

Space

O(L)

Trade-offs

Pros

No external utilities are needed; it's a pure bash solution.

Cons

Significantly slower than using dedicated text-processing tools like grep, sed, or awk, especially for large files.
The one-liner syntax can be less readable.

This approach uses awk, a powerful pattern-scanning and processing language. awk can filter lines based on a regular expression. By default, awk prints any line that matches the provided pattern.

Algorithm

1. Invoke awk with a script that consists of a single pattern-action rule.
1. The pattern is the regular expression /^($[0-9]{3}$ [0-9]{3}-[0-9]{4}|[0-9]{3}-[0-9]{3}-[0-9]{4})$/.
1. The action is omitted, which defaults to { print $0 } (print the current line).
1. awk reads file.txt line by line.
1. For each line, it tests if it matches the pattern.
1. If a match is found, the default action is executed, printing the line.

Walkthrough

awk processes the input file line by line. The core of the command is awk '/pattern/' file.txt. The pattern is a regular expression enclosed in slashes: /^($[0-9]{3}$ [0-9]{3}-[0-9]{4}|[0-9]{3}-[0-9]{3}-[0-9]{4})$/. awk evaluates this pattern for each line. If the pattern matches the line, awk's default action is to print the entire line (print $0), which is exactly what is needed. The regex is anchored with ^ and $ to match the whole line.

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

Complexity

Time

O(N * L)

Space

O(L)

Trade-offs

Pros

Concise and readable one-liner.
awk is a standard and powerful tool available on most Unix-like systems.

Cons

Generally slightly slower than sed or grep for simple line filtering because awk is a more feature-rich tool.

This approach utilizes sed (Stream Editor), a classic Unix utility for parsing and transforming text. We can use sed to filter and print only the lines that match the specified pattern.

Algorithm

1. Invoke sed with the -n (no-print) and -r (extended-regex) flags.
1. Provide the script '/pattern/p'.
1. sed reads file.txt line by line into its pattern space.
1. For each line, it checks if the content of the pattern space matches the regex ^($[0-9]{3}$ [0-9]{3}-[0-9]{4}|[0-9]{3}-[0-9]{3}-[0-9]{4})$.
1. If there is a match, the p command is executed, which prints the pattern space (the current line).
1. If there is no match, nothing is printed for that line (due to the -n flag).

Walkthrough

The sed command is used with the -n option to suppress the default behavior of printing every line. The -r (or -E on BSD/macOS) option is used to enable extended regular expressions, which makes the pattern more readable. The script provided to sed is '/pattern/p'. This tells sed to print (p) only the lines that match the pattern. The pattern is the same regex used in the other approaches: ^($[0-9]{3}$ [0-9]{3}-[0-9]{4}|[0-9]{3}-[0-9]{3}-[0-9]{4})$. The command effectively filters the input file, printing only the valid phone numbers.

sed -n -r '/^(\([0-9]{3}\) [0-9]{3}-[0-9]{4}|[0-9]{3}-[0-9]{3}-[0-9]{4})$/p' file.txt

Complexity

Time

O(N * L)

Space

O(L)

Trade-offs

Pros

Very efficient and concise.
sed is a standard, powerful tool.

Cons

The syntax (-n and /p) can be slightly less intuitive than grep for beginners.
The flag for extended regex can differ between systems (-r for GNU sed, -E for BSD sed).

The most direct and typically most efficient approach is to use grep, the standard Unix utility for finding lines that match a regular expression.

Algorithm

1. Invoke grep with the -E flag for extended regular expressions.
1. Provide the regex pattern to match. The pattern ^($[0-9]{3}$ [0-9]{3}-[0-9]{4}|[0-9]{3}-[0-9]{3}-[0-9]{4})$ combines the two valid formats with an OR (|) and anchors the match to the beginning (^) and end ($) of the line.
1. Specify the input file, file.txt.
1. grep reads the file line by line, applies the regex, and prints any matching lines to standard output.

Walkthrough

grep is designed specifically for this task: searching for patterns in text. We use the -E flag (or egrep) to enable extended regular expressions, which allows for features like | (OR) and () (grouping) without backslashes. The regular expression ^($[0-9]{3}$ [0-9]{3}-[0-9]{4}|[0-9]{3}-[0-9]{3}-[0-9]{4})$ is passed to grep. The ^ and $ anchors are crucial to ensure that the entire line matches one of the valid phone number formats, preventing partial matches within a longer, invalid line. grep will then read file.txt and print only the lines that fully match this pattern. An alternative, slightly more compact regex can also be used: ^($[0-9]{3}$ |[0-9]{3}-)[0-9]{3}-[0-9]{4}$.

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

Complexity

Time

O(N * L)

Space

O(L)

Trade-offs

Pros

Most idiomatic and efficient solution for this task.
The command's purpose is immediately clear.
grep is universally available on Unix-like systems.

Cons

None for this particular problem.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem