1694. 重新格式化电话号码

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 的分组。分组是 "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" 。

提示：

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

解题思路

这道题的核心思路是按照特定规则对电话号码进行分组格式化。

解题步骤：

预处理：首先移除所有空格和破折号，只保留数字字符
分组规则：按照题目要求进行分组
- 当剩余数字超过4位时，每次取3位作为一组
- 当剩余数字恰好为4位时，分成两个2位的组（避免产生1位的组）
- 当剩余数字为2或3位时，直接作为一组

关键点分析：

题目强调不能产生长度为1的块，所以当剩余4位时必须分成2+2，而不是3+1
最多产生两个长度为2的块，这个约束在按规则操作时自然满足
使用while循环不断处理剩余数字，根据剩余长度选择合适的分组策略

算法流程：

遍历原字符串，提取所有数字字符
使用while循环处理数字字符串：
- 如果剩余长度>4：取前3位加入结果
- 如果剩余长度=4：取前2位，剩下2位下轮处理
- 如果剩余长度≤3：取完所有剩余位
用破折号连接各个分组

代码实现

class Solution {
public:
    string reformatNumber(string number) {
        string digits = "";
        for (char c : number) {
            if (isdigit(c)) {
                digits += c;
            }
        }
        
        vector<string> groups;
        int i = 0;
        while (i < digits.length()) {
            int remaining = digits.length() - i;
            if (remaining > 4) {
                groups.push_back(digits.substr(i, 3));
                i += 3;
            } else if (remaining == 4) {
                groups.push_back(digits.substr(i, 2));
                i += 2;
            } else {
                groups.push_back(digits.substr(i));
                break;
            }
        }
        
        string result = "";
        for (int i = 0; i < groups.size(); i++) {
            if (i > 0) result += "-";
            result += groups[i];
        }
        return result;
    }
};

class Solution:
    def reformatNumber(self, number: str) -> str:
        digits = ''.join(c for c in number if c.isdigit())
        
        groups = []
        i = 0
        while i < len(digits):
            remaining = len(digits) - i
            if remaining > 4:
                groups.append(digits[i:i+3])
                i += 3
            elif remaining == 4:
                groups.append(digits[i:i+2])
                i += 2
            else:
                groups.append(digits[i:])
                break
        
        return '-'.join(groups)

public class Solution {
    public string ReformatNumber(string number) {
        string digits = "";
        foreach (char c in number) {
            if (char.IsDigit(c)) {
                digits += c;
            }
        }
        
        List<string> groups = new List<string>();
        int i = 0;
        while (i < digits.Length) {
            int remaining = digits.Length - i;
            if (remaining > 4) {
                groups.Add(digits.Substring(i, 3));
                i += 3;
            } else if (remaining == 4) {
                groups.Add(digits.Substring(i, 2));
                i += 2;
            } else {
                groups.Add(digits.Substring(i));
                break;
            }
        }
        
        return string.Join("-", groups);
    }
}

/**
 * @param {string} number
 * @return {string}
 */
var reformatNumber = function(number) {
    const digits = number.replace(/[\s-]/g, '');
    const blocks = [];
    let i = 0;
    
    while (digits.length - i > 4) {
        blocks.push(digits.slice(i, i + 3));
        i += 3;
    }
    
    const remaining = digits.length - i;
    if (remaining === 2) {
        blocks.push(digits.slice(i));
    } else if (remaining === 3) {
        blocks.push(digits.slice(i));
    } else if (remaining === 4) {
        blocks.push(digits.slice(i, i + 2));
        blocks.push(digits.slice(i + 2));
    }
    
    return blocks.join('-');
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	大小
时间复杂度	O(n)
空间复杂度	O(n)

其中 n 是输入字符串的长度。我们需要遍历字符串一次提取数字，然后再次遍历进行分组，空间复杂度主要用于存储提取的数字和分组结果。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析