Problem 193

Abstract / Summary

Check if a string matches one of several allowed phone number formats.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Bash 0193.bash

egrep "^((\([[:digit:]]{3}\) )|([[:digit:]]{3}\-))[[:digit:]]{3}\-[[:digit:]]{4}$" file.txt
1 lines | 93 bytes | submitted September 6, 2023 | GitHub  

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 30% (400k+ submissions).

Typical patterns to solve this problem:
  • Shell
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The command shown invokes egrep to filter lines from file.txt that conform to a specific telephone-number format. The regular expression is anchored at both the start (^) and end ($) of each line, ensuring that only complete matches are returned. By using the extended regular-expression syntax (egrep), the pattern can express alternation and grouping without excessive escaping, which keeps the expression concise and improves readability.

Key Steps

Invocation of the Pattern Matcher

egrep "^((\([[:digit:]]{3}\) )|([[:digit:]]{3}\-))[[:digit:]]{3}\-[[:digit:]]{4}$" file.txt

The command launches egrep, which reads file.txt line by line, applies the supplied pattern, and prints each line that satisfies the pattern. Because the pattern is quoted, the shell does not interpret any of the special characters, allowing the regular expression engine to process them directly.

Construction of the Regular Expression

The pattern consists of three logical parts: a leading area-code segment, a central-office segment, and a line-number segment.

The leading segment is expressed as an alternation between a parenthesized area code followed by a space and a plain three-digit area code followed by a hyphen:

((\([[:digit:]]{3}\) )|([[:digit:]]{3}\-))

The central-office segment is a fixed three-digit block:

[[:digit:]]{3}

The line-number segment is a fixed four-digit block preceded by a hyphen:

\-[[:digit:]]{4}

When concatenated and anchored, the full expression matches strings such as

(123) 456-7890
123-456-7890

File Processing

egrep streams the input file, evaluating each line independently. The anchored pattern guarantees that partial matches inside longer strings are ignored, so only lines that exactly match the telephone format are emitted.

Edge Cases Handled

The expression deliberately accounts for two common representations of North-American telephone numbers. By allowing either a parenthesized area code with a trailing space or a plain area code with a hyphen, the command accepts both styles without ambiguity. The use of [[:digit:]] rather than \d ensures compatibility with locales where digit character classes are defined, covering any Unicode digit that belongs to the current locale’s digit set. The anchors (^ and $) prevent matches on lines that contain additional characters before or after the phone number, such as surrounding whitespace or comments.

Performance Optimizations

Choosing egrep (the extended-regex variant) eliminates the need for backslashes before the alternation operator (|) and grouping parentheses, reducing the amount of parsing the regex engine must perform. The pattern is fully anchored, allowing the engine to reject non-matching lines early without scanning the entire line. The character class [[:digit:]] is a pre-compiled set, enabling fast membership tests for each character. By specifying exact quantifiers ({3} and {4}) the engine can allocate fixed-size buffers for the digit groups, avoiding the overhead of variable-length backtracking. The alternation is limited to two simple alternatives, each of which is a straightforward literal sequence, further minimizing the search space during matching.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you have a giant toy box filled with hundreds of pieces of paper, and you want to find all the secret notes that have a phone number written on them. This little computer command is like a tiny robot detective that looks through your pile. It reads every single line in your file and checks to see if the characters on the page follow the special pattern of a phone number.

The part inside the quotes is a set of instructions for the detective. It tells the robot that it is looking for a specific shape, like a group of three numbers inside round parentheses or three numbers followed by a little dash. After that, it looks for three more numbers, then another dash, and finally four numbers at the end. If the detective sees a line that matches this exact pattern, it grabs that line and shows it to you on the screen so you can see it. It is just a very fast way to sort through a messy pile of information to find exactly what you need.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 20 | median = 6.5 | μ = 6.20 | σ = 1.96

Complexity Analysis

not analyzed yet

Solved On The Same Day

25 easy 22 medium 5 hard
53 solutions   September 6, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality