重新格式化电话号码

难度: Easy

给你一个字符串形式的电话号码 number 。number 由数字、空格 ' '、和破折号 '-' 组成。

请你按下述方式重新格式化电话号码。

首先，删除所有的空格和破折号。
其次，将数组从左到右 每 3 个一组 分块，直到剩下 4 个或更少数字。剩下的数字将按下述规定再分块：
- 2 个数字：单个含 2 个数字的块。
- 3 个数字：单个含 3 个数字的块。
- 4 个数字：两个分别含 2 个数字的块。

最后用破折号将这些块连接起来。注意，重新格式化过程中 不应该 生成仅含 1 个数字的块，并且最多生成两个含 2 个数字的块。

返回格式化后的电话号码。

示例 1：

输入：number = "1-23-45 6"
输出："123-456"
解释：数字是 "123456"
步骤 1：共有超过 4 个数字，所以先取 3 个数字分为一组。第 1 个块是 "123" 。
步骤 2：剩下 3 个数字，将它们放入单个含 3 个数字的块。第 2 个块是 "456" 。
连接这些块后得到 "123-456" 。

示例 2：

输入：number = "123 4-567"
输出："123-45-67"
解释：数字是 "1234567".
步骤 1：共有超过 4 个数字，所以先取 3 个数字分为一组。第 1 个块是 "123" 。
步骤 2：剩下 4 个数字，所以将它们分成两个含 2 个数字的块。这 2 块分别是 "45" 和 "67" 。
连接这些块后得到 "123-45-67" 。

示例 3：

输入：number = "123 4-5678"
输出："123-456-78"
解释：数字是 "12345678" 。
步骤 1：第 1 个块 "123" 。
步骤 2：第 2 个块 "456" 。
步骤 3：剩下 2 个数字，将它们放入单个含 2 个数字的块。第 3 个块是 "78" 。
连接这些块后得到 "123-456-78" 。

示例 4：

输入：number = "12"
输出："12"

示例 5：

输入：number = "--17-5 229 35-39475 "
输出："175-229-353-94-75"

提示：

2 <= number.length <= 100
number 由数字和字符 '-' 及 ' ' 组成。
number 中至少含 2 个数字。

Submission

运行时间: 24 ms

内存: 0.0 MB

class Solution:
    def reformatNumber(self, number: str) -> str:
        return re.sub('(...?(?=..))', r'\1-', re.sub('\D', '', number))

Explain

题解采用了正则表达式进行处理。首先，使用 re.sub('\D', '', number) 删除输入字符串中所有非数字的字符，包括空格和破折号。然后，使用另一个正则表达式 re.sub('(...?(?=..))', r'\1-', ...) 在适当的位置插入破折号。这个正则表达式分为两部分：'...?' 匹配2到3个数字；'(?=..)' 是正向前瞻，确保后面至少还有两个字符，这样可以保证不会在字符串末尾添加破折号。通过这种方式，能够正确地将字符串分组为每三个数字一组，直到最后剩余的数字按题目要求进行特殊处理。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def reformatNumber(self, number: str) -> str:
        # 删除所有非数字字符
        digits_only = re.sub('\D', '', number)
        # 每3个数字分一组，最后处理2或4个数字的情况
        return re.sub('(...?(?=..))', r'\1-', digits_only)

Explore

正则表达式`(...?(?=..))`中的`...?`部分可以匹配2到3个数字。其关键在于正向前瞻`(?=..)`，这保证在当前匹配后至少还有两个数字。当数字总数为4时，首次匹配会捕获前两个数字（因为如果匹配3个，后面就剩一个，不满足前瞻条件），然后剩余两个数字在下一次迭代中被处理。因此，这种方法自然而然地将4个数字分为两组，每组两个。

在这种情况下，正则表达式`(...?(?=..))`确保只在至少后续有两个数字时才插入破折号。例如输入'123456789'，处理过程如下：首先`123`匹配并插入破折号得到`123-`，接着`456`匹配得到`123-456-`，然后`789`匹配，因为之后没有额外数字，所以不再添加破折号，最终输出为`123-456-789`。此方法不会在末尾引入非预期的破折号。

正则表达式的前瞻`(?=..)`部分是一个断言，用来检查当前匹配点之后的内容。具体来说，`(?=..)`要求在当前匹配的位置之后至少还有两个字符。这种方式确保了只有在至少后面还有两个数字的情况下才会在匹配的数字后添加破折号。这样，当字符串末尾少于三个数字且无法满足该前瞻条件时，就不会添加破折号，避免了在末尾产生非预期的破折号。

对于极短的输入字符串，例如只有一个或两个数字，正则表达式`(...?(?=..))`中的前瞻`(?=..)`无法满足，因此这部分正则表达式不会执行任何匹配，也就不会添加任何破折号。在这种情况下，`re.sub`简单地返回原始数字字符串，因为没有满足条件的部分来插入破折号。因此，算法已经能够适应这些特殊情况，无需额外添加特定条件。