0193. Valid Phone Numbers

题目信息

题号:
  1. 有效电话号码

难度:

Easy

主题:

Shell、扩展正则表达式、整行匹配

原题:

LeetCode 0193

重点:

把两种合法格式合并为带锚点的整行正则,精确区分分组符号与数字位数

题目重述

编写 Bash 脚本读取 file.txt,文件每行是一个候选电话号码。只输出严格符合以下任一 格式的完整行:

  • xxx-xxx-xxxx;

  • (xxx) xxx-xxxx。

每个 x 都必须是十进制数字;括号格式的右括号后恰好有一个空格。包含额外前后缀、 空格、字母或错误分组的行都不合法。输出保持原文件顺序。

自建示例

file.txt:
415-208-7391
(212) 555-0198
212 555-0198
(646)-555-0100
800-12-34567
x415-208-7391

输出:
415-208-7391
(212) 555-0198

Bash 实现

#!/usr/bin/env bash

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

题解

目标是验证整行而不是搜索片段

若只搜索 [0-9]{3}-[0-9]{3}-[0-9]{4},字符串 x415-208-7391-extra 中仍含一个合法形状的子串,却不应整行输出。题目的候选单位是文件 中的一整行,所以正则必须同时描述格式和边界。

可以分别运行两次 grep 处理两种格式,但结果会按两次命令分组,不再自然保持原文件 中的统一顺序;以后若分支重叠,还可能重复输出。单个扩展正则在一次扫描中判断两个分支, 每个合法原始行只被 grep 原样输出一次。

先提取两种格式的共同后缀

两种格式都以 三位数字-四位数字 结束,即:

[0-9]{3}-[0-9]{4}

差异只在开头区域码部分:

[0-9]{3}-       普通格式,例如 415-
\([0-9]{3}\)   括号格式,例如 (212) 后跟一个空格

用扩展正则分组和选择符合并后得到:

([0-9]{3}-|\([0-9]{3}\) )[0-9]{3}-[0-9]{4}

括号格式分支中的空格写在 \) 之后,表示必须恰好存在一个普通空格;连字符格式分支则 没有该空格。

锚点删除额外字符

^ 要求匹配从行首开始,$ 要求在行尾结束。两者把“行内存在合法片段”收紧为“整行 就是合法号码”:

  • x415-208-7391 因行首多字符失败;

  • 415-208-7391 extra 因行尾多字符失败;

  • 前导、尾随空格也不属于两个格式,都会失败。

[0-9] 明确表示十进制数字;{3}、{4} 固定每组位数。命令使用 grep -E 启用扩展正则,使 |、分组括号和重复次数可按该语法工作。

转义的两个层次

扩展正则中的未转义圆括号用于分组,因此电话号码里需要匹配的字面括号写成 \(、 \)。整个模式由 Shell 单引号包围,反斜杠会原样传给 grep,不会先被 Shell 消耗。

外层未转义的 (...) 是两个格式分支的正则分组,内层 \(...\) 才是电话号码字符。 混淆两者会让模式把括号当控制语法,错误接受没有字面括号的文本。

具体行走读

415-208-7391 走第一个分支:三位数字加连字符,然后匹配共同后缀。 (212) 555-0198 走第二个分支:字面左括号、三位数字、字面右括号、一个空格,再匹配 后缀。

212 555-0198 的区域码后是空格而不是连字符,也没有括号,两个分支都失败; (646)-555-0100 的右括号后是连字符而不是规定空格,同样失败;800-12-34567 的 数字组长度不符合 3-3-4。

输出与复杂度

grep 对每行做匹配,命中时默认输出原始整行,因此无需 sed 或 awk 重建号码, 原文件顺序也自然保持。设文件总字符数为 L,固定结构正则的一次流式扫描可视为 O(L) 时间;除匹配器固定状态和输出缓冲外,不保存随文件行数增长的集合。