题目

标题和出处

标题：重新格式化电话号码

出处：1694. 重新格式化电话号码

难度

3 级

题目描述

要求

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

请你按下述方式重新格式化电话号码。首先，删除所有的空格和破折号。其次，将数字从左到右每 个一组分块，直到剩下 个或更少数字。剩下的数字将按下述规定再分块：

• 个数字：单个含 个数字的块。
• 个数字：单个含 个数字的块。
• 个数字：两个分别含 个数字的块。

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

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

示例

示例 1：

输入：
输出：
解释：数字是 。
步骤 ：共有超过 个数字，所以先取 个数字分为一组。第 个块是 。
步骤 ：剩下 个数字，将它们放入单个含 个数字的块。第 个块是 。
连接这些块后得到 。

示例 2：

输入：
输出：
解释：数字是 。
步骤 ：共有超过 个数字，所以先取 个数字分为一组。第 个块是 。
步骤 ：剩下 个数字，所以将它们分成两个含 个数字的块。这 块分别是 和 。
连接这些块后得到 。

示例 3：

输入：
输出：
解释：数字是 。
步骤 ：第 个块是 。
步骤 ：第 个块是 。
步骤 ：剩下 个数字，将它们放入单个含 个数字的块。第 个块是 。
连接这些块后得到 。

示例 4：

输入：
输出：

示例 5：

输入：
输出：

数据范围

• 
• 由数字和字符 及 组成
• 中至少含 个数字

解法

思路和算法

由于在格式化电话号码时，只考虑电话号码中的数字，因此只需要知道电话号码中的数字有多少个，即可知道应该如何格式化。遍历原始电话号码 ，统计数字的个数。

得到数字的个数之后，即可按照如下步骤生成格式化的电话号码。

1. 当剩余的数字大于 个时，总是将数字按照每 个一组分块，因此遍历电话号码并生成含 个数字的块，得到一个含 个数字的块之后，则添加一个破折号。由于该操作是在剩余的数字大于 个时进行的，因此每次添加破折号之后，一定还有剩余的数字，即格式化的电话号码不会以破折号结尾。
2. 当剩余的数字不超过 个时，剩余的数字可能是 个、 个或 个。当剩余 个数字时，可以生成 个块，当剩余 个或 个数字时，只可以生成 个块。因此当剩余 个数字时，继续遍历电话号码，再处理出一个含 个数字的块，然后添加一个破折号，则剩下 个数字。
3. 当剩余的数字为 个或 个时，剩余的数字只能生成 个块，因此遍历电话号码的剩余部分直到结束，将剩余的数字全部添加到最后一个块即可。

如果电话号码中的数字大于 个，步骤 1 必定会执行，然后执行步骤 2 和步骤 3，或者只执行步骤 3。具体为，当电话号码中的数字个数除以 的余数为 时，会执行步骤 2 和步骤 3，当电话号码中的数字个数除以 的余数不为 时，只会执行步骤 3。

如果电话号码中的数字等于 个，则只会执行步骤 2 和步骤 3。

如果电话号码中的数字等于 个或 个，则只会执行步骤 3。

代码

class Solution {
    public String reformatNumber(String number) {
        final int BLOCK_SIZE = 3, SMALL_BLOCK_SIZE = 2;
        int digits = 0;
        int length = number.length();
        for (int i = 0; i < length; i++) {
            char c = number.charAt(i);
            if (Character.isDigit(c)) {
                digits++;
            }
        }
        StringBuffer sb = new StringBuffer();
        int index = 0;
        while (digits > 4) {
            int curBlockSize = BLOCK_SIZE;
            while (curBlockSize > 0) {
                char c = number.charAt(index);
                if (Character.isDigit(c)) {
                    sb.append(c);
                    curBlockSize--;
                }
                index++;
            }
            digits -= BLOCK_SIZE;
            sb.append('-');
        }
        if (digits == 4) {
            int curBlockSize = SMALL_BLOCK_SIZE;
            while (curBlockSize > 0) {
                char c = number.charAt(index);
                if (Character.isDigit(c)) {
                    sb.append(c);
                    curBlockSize--;
                }
                index++;
            }
            digits -= SMALL_BLOCK_SIZE;
            sb.append('-');
        }
        while (index < length) {
            char c = number.charAt(index);
            if (Character.isDigit(c)) {
                sb.append(c);
            }
            index++;
        }
        return sb.toString();
    }
}

复杂度分析

• 时间复杂度：#card=math&code=O%28n%29&id=xs65C)，其中 是字符串 的长度。需要遍历字符串 两次。
• 空间复杂度：#card=math&code=O%28n%29&id=v2ymV)，其中 是字符串 的长度。需要额外创建一个长度为 #card=math&code=O%28n%29&id=rmlAA) 的 或 类型的对象用于存储格式化后的电话号码。由于 Java 中的 类型的对象不可变，因此空间复杂度至少为 #card=math&code=O%28n%29&id=sRLNc)。