Valid Phone Numbers - Solution & Explanation

Problem Overview: You receive a text file where each line may contain a phone number. Print only the lines that match valid U.S. formats: xxx-xxx-xxxx or (xxx) xxx-xxxx. Any line that does not strictly follow one of these patterns must be ignored.

Approach 1: Regular Expression Matching (O(n * m) time, O(1) space)

The most direct solution uses a regular expression to validate the exact structure of each line. The regex anchors the pattern with ^ and $ so partial matches are rejected. The two valid formats are captured using alternation: ^([0-9]{3}-[0-9]{3}-[0-9]{4}|\([0-9]{3}\) [0-9]{3}-[0-9]{4})$. In Shell, tools like grep -E, awk, or sed iterate through each line and print matches. The algorithm scans every line once (n lines, m characters per line), making the runtime O(n * m) with constant auxiliary space.

Approach 2: Manual Pattern Validation (O(n * m) time, O(1) space)

In languages such as Python, Java, C++, or JavaScript, you can validate the format manually without regex. Iterate through each line and check its structure character by character. For the xxx-xxx-xxxx format, confirm digits at indices 0–2, 4–6, and 8–11, and hyphens at indices 3 and 7. For the (xxx) xxx-xxxx format, check parentheses at indices 0 and 4, a space at index 5, and hyphens at index 9 while verifying digits in the remaining positions. This method uses basic string indexing and conditional checks. Time complexity remains O(n * m) because every character may be inspected once.

Recommended for interviews: The regex approach is what interviewers typically expect for the Shell version of the problem. It demonstrates familiarity with pattern matching tools like grep and shows you can encode strict format constraints concisely. Implementing manual validation helps show deeper understanding of string parsing, but regex is the fastest and most idiomatic solution for this task.