LeetCode 1694: Reformat Phone Number (Block Grouping Simulation)
LeetCode 1694StringSimulationToday we solve LeetCode 1694 - Reformat Phone Number.
Source: https://leetcode.com/problems/reformat-phone-number/
English
Problem Summary
Given a phone number string containing digits, spaces, and dashes, remove non-digits and regroup digits from left to right. Each block should be length 3 until the remaining digits are 2, 3, or 4. If 4 remain, split as 2-2.
Key Insight
This is a deterministic simulation problem. After filtering digits, only one rule matters: never leave a final block of length 1. So while remaining digits are greater than 4, emit 3-digit blocks; then handle the tail as either 2, 3, or 2+2.
Algorithm
- Extract all digits into a clean sequence.
- While remaining length > 4, append a 3-digit block.
- If remaining length is 4, append two 2-digit blocks.
- Otherwise append one final block (length 2 or 3).
- Join blocks with dashes.
Complexity Analysis
Let n be the input length.
Time: O(n).
Space: O(n) for filtered digits and output.
Common Pitfalls
- Producing a trailing 1-digit block (invalid).
- Forgetting to remove spaces and dashes first.
- Mishandling the 4-digit tail (must be 2-2, not 3-1).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String reformatNumber(String number) {
StringBuilder digits = new StringBuilder();
for (char ch : number.toCharArray()) {
if (Character.isDigit(ch)) digits.append(ch);
}
StringBuilder ans = new StringBuilder();
int i = 0, n = digits.length();
while (n - i > 4) {
ans.append(digits, i, i + 3).append('-');
i += 3;
}
if (n - i == 4) {
ans.append(digits, i, i + 2).append('-').append(digits, i + 2, i + 4);
} else {
ans.append(digits.substring(i));
}
return ans.toString();
}
}func reformatNumber(number string) string {
digits := make([]byte, 0, len(number))
for i := 0; i < len(number); i++ {
ch := number[i]
if ch >= '0' && ch <= '9' {
digits = append(digits, ch)
}
}
var b strings.Builder
i, n := 0, len(digits)
for n-i > 4 {
b.Write(digits[i : i+3])
b.WriteByte('-')
i += 3
}
if n-i == 4 {
b.Write(digits[i : i+2])
b.WriteByte('-')
b.Write(digits[i+2 : i+4])
} else {
b.Write(digits[i:n])
}
return b.String()
}class Solution {
public:
string reformatNumber(string number) {
string digits;
for (char ch : number) {
if (isdigit(static_cast<unsigned char>(ch))) digits.push_back(ch);
}
string ans;
int i = 0, n = static_cast<int>(digits.size());
while (n - i > 4) {
ans += digits.substr(i, 3);
ans.push_back('-');
i += 3;
}
if (n - i == 4) {
ans += digits.substr(i, 2);
ans.push_back('-');
ans += digits.substr(i + 2, 2);
} else {
ans += digits.substr(i);
}
return ans;
}
};class Solution:
def reformatNumber(self, number: str) -> str:
digits = [ch for ch in number if ch.isdigit()]
ans = []
i, n = 0, len(digits)
while n - i > 4:
ans.append(''.join(digits[i:i + 3]))
i += 3
if n - i == 4:
ans.append(''.join(digits[i:i + 2]))
ans.append(''.join(digits[i + 2:i + 4]))
else:
ans.append(''.join(digits[i:]))
return '-'.join(ans)var reformatNumber = function(number) {
const digits = [];
for (const ch of number) {
if (ch >= '0' && ch <= '9') digits.push(ch);
}
const parts = [];
let i = 0;
while (digits.length - i > 4) {
parts.push(digits.slice(i, i + 3).join(''));
i += 3;
}
if (digits.length - i === 4) {
parts.push(digits.slice(i, i + 2).join(''));
parts.push(digits.slice(i + 2, i + 4).join(''));
} else {
parts.push(digits.slice(i).join(''));
}
return parts.join('-');
};中文
题目概述
给定一个包含数字、空格和短横线的电话号码字符串，先去掉非数字字符，再从左到右重新分组。优先分成长度为 3 的块；当剩余位数是 2、3 或 4 时收尾，其中 4 必须拆成 2-2。
核心思路
这是规则明确的模拟题。关键是避免最后出现长度为 1 的分组。做法是先提取纯数字，再在“剩余位数大于 4”时持续取 3 位，最后统一处理尾巴。
算法步骤
- 遍历字符串，提取全部数字字符。
- 当剩余位数 > 4 时，每次加入一个 3 位分组。
- 若剩余位数为 4，拆成两个 2 位分组。
- 否则直接加入最后一个 2 位或 3 位分组。
- 用 - 连接所有分组并返回。
复杂度分析
设输入长度为 n。
时间复杂度：O(n)。
空间复杂度：O(n)（存储数字与结果）。
常见陷阱
- 末尾错误地保留 1 位分组。
- 没有先过滤空格和短横线。
- 对 4 位尾部处理错误，写成 3-1 而不是 2-2。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String reformatNumber(String number) {
StringBuilder digits = new StringBuilder();
for (char ch : number.toCharArray()) {
if (Character.isDigit(ch)) digits.append(ch);
}
StringBuilder ans = new StringBuilder();
int i = 0, n = digits.length();
while (n - i > 4) {
ans.append(digits, i, i + 3).append('-');
i += 3;
}
if (n - i == 4) {
ans.append(digits, i, i + 2).append('-').append(digits, i + 2, i + 4);
} else {
ans.append(digits.substring(i));
}
return ans.toString();
}
}func reformatNumber(number string) string {
digits := make([]byte, 0, len(number))
for i := 0; i < len(number); i++ {
ch := number[i]
if ch >= '0' && ch <= '9' {
digits = append(digits, ch)
}
}
var b strings.Builder
i, n := 0, len(digits)
for n-i > 4 {
b.Write(digits[i : i+3])
b.WriteByte('-')
i += 3
}
if n-i == 4 {
b.Write(digits[i : i+2])
b.WriteByte('-')
b.Write(digits[i+2 : i+4])
} else {
b.Write(digits[i:n])
}
return b.String()
}class Solution {
public:
string reformatNumber(string number) {
string digits;
for (char ch : number) {
if (isdigit(static_cast<unsigned char>(ch))) digits.push_back(ch);
}
string ans;
int i = 0, n = static_cast<int>(digits.size());
while (n - i > 4) {
ans += digits.substr(i, 3);
ans.push_back('-');
i += 3;
}
if (n - i == 4) {
ans += digits.substr(i, 2);
ans.push_back('-');
ans += digits.substr(i + 2, 2);
} else {
ans += digits.substr(i);
}
return ans;
}
};class Solution:
def reformatNumber(self, number: str) -> str:
digits = [ch for ch in number if ch.isdigit()]
ans = []
i, n = 0, len(digits)
while n - i > 4:
ans.append(''.join(digits[i:i + 3]))
i += 3
if n - i == 4:
ans.append(''.join(digits[i:i + 2]))
ans.append(''.join(digits[i + 2:i + 4]))
else:
ans.append(''.join(digits[i:]))
return '-'.join(ans)var reformatNumber = function(number) {
const digits = [];
for (const ch of number) {
if (ch >= '0' && ch <= '9') digits.push(ch);
}
const parts = [];
let i = 0;
while (digits.length - i > 4) {
parts.push(digits.slice(i, i + 3).join(''));
i += 3;
}
if (digits.length - i === 4) {
parts.push(digits.slice(i, i + 2).join(''));
parts.push(digits.slice(i + 2, i + 4).join(''));
} else {
parts.push(digits.slice(i).join(''));
}
return parts.join('-');
};
Comments