LeetCode 193. 有效电话号码
目录
题目描述
题意分析
文件
file.txt每行是一个电话号码，合法格式只有两种：xxx-xxx-xxxx或(xxx) xxx-xxxx，其中每个x都必须是十进制数字。题目保证每行前后没有多余空格。这不是“行中包含一个电话号码”即可，而是整行必须完整符合格式。因此正则必须同时使用
^、$锚定行首和行尾，否则abc987-123-4567xyz也可能被误匹配。两种格式只有前半段不同：要么是
三位数字 + 连字符，要么是左括号 + 三位数字 + 右括号 + 一个空格；后半段共同为三位数字-四位数字。把公共后缀提出来，可以避免写两份重复正则。官方样例中的
987-123-4567、(123) 456-7890合法，而123 456 7890因分隔符不符合任一格式被过滤。
解法：grep 扩展正则匹配整行
核心思路
使用
grep -E启用扩展正则表达式。前缀写成两个分支：
\([0-9]{3}\)匹配(123)，括号需要转义，右括号后必须恰好有一个空格；[0-9]{3}-匹配123-。两个分支之后共享
[0-9]{3}-[0-9]{4}。最外层用^...$包围，保证行内没有额外字符。这里使用
[0-9]而不是\d：\d属于 PCRE 等方言，在 POSIX ERE 的grep -E中不具备可移植的“数字”含义。
解题步骤
- 用
^固定匹配起点为行首。- 匹配括号格式或连字符格式的三位区号。
- 匹配公共的
三位数字-四位数字后缀。- 用
$要求匹配在行尾结束。grep原样输出所有匹配行，无需额外awk或sed。
代码实现
grep -E '^(\([0-9]{3}\) |[0-9]{3}-)[0-9]{3}-[0-9]{4}$' file.txt
复杂度分析
- 时间复杂度：$O(N)$，其中 $N$ 是文件总字符数；正则长度固定，
grep逐行扫描每个字符常数次。- 空间复杂度：相对整个文件为 $O(L)$，其中 $L$ 是最长单行长度，工具只需缓冲当前行；固定正则本身占 $O(1)$ 空间。
关键点总结
- 整行格式校验必须使用首尾锚点，不能只匹配一个合法子串。
- 括号在正则中有分组含义，匹配字面括号必须写成
\(、\)。(xxx)后的空格属于格式的一部分，不能写成任意空白或直接省略。- 把两个格式的公共后缀提取出来，能显著降低分支写错的概率。
- 面试追问可移植性时，说明
grep -E使用 POSIX ERE；grep -P和\d依赖 PCRE 支持，并非所有 Unix 环境都有。
易错点总结
- 省略
^或$：tel: 987-123-4567会因包含合法子串而被误判，但整行格式并不合法。- 忘记转义括号：
([0-9]{3})在正则中只是分组，不会要求输入真的出现(、)。- 使用
\d配合grep -E：在 POSIX ERE 中它不是可移植的数字类，应使用[0-9]。- 漏掉右括号后的空格：会错误接受
(123)456-7890，同时拒绝题目规定的(123) 456-7890写法。- 把连字符写成可选：例如
[ -]?会额外接受123 456-7890或1234567890，超出题目允许的两种格式。- 使用基本
grep却保留 ERE 的|、{3}写法：不同实现下可能按字面量解释；应显式加-E。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 192. 统计词频 | 中等 | Shell 管道中的分词、聚合和排序 |
| 194. 转置文件 | 中等 | 使用 awk 动态字段访问重组文本 |
| 195. 第十行 | 简单 | 按精确行号筛选并提前结束读取 |