0193. Valid Phone Numbers ========================= 题目信息 -------- :题号: 0193. 有效电话号码 :难度: Easy :主题: Shell、扩展正则表达式、整行匹配 :原题: `LeetCode 0193 `_ :重点: 把两种合法格式合并为带锚点的整行正则,精确区分分组符号与数字位数 题目重述 -------- 编写 Bash 脚本读取 ``file.txt``,文件每行是一个候选电话号码。只输出严格符合以下任一 格式的完整行: * ``xxx-xxx-xxxx``; * ``(xxx) xxx-xxxx``。 每个 ``x`` 都必须是十进制数字;括号格式的右括号后恰好有一个空格。包含额外前后缀、 空格、字母或错误分组的行都不合法。输出保持原文件顺序。 自建示例 -------- .. code-block:: text 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 实现 --------- .. code-block:: 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`` 原样输出一次。 先提取两种格式的共同后缀 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 两种格式都以 ``三位数字-四位数字`` 结束,即: .. code-block:: text [0-9]{3}-[0-9]{4} 差异只在开头区域码部分: .. code-block:: text [0-9]{3}- 普通格式,例如 415- \([0-9]{3}\) 括号格式,例如 (212) 后跟一个空格 用扩展正则分组和选择符合并后得到: .. code-block:: text ([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)`` 时间;除匹配器固定状态和输出缓冲外,不保存随文件行数增长的集合。