LeetCode 1694 - Reformat Phone Number
The problem requires reformatting a phone number string in a specific structured way. The input is a string number conta
Difficulty: 🟢 Easy
Topics: String
Solution
Problem Understanding
The problem requires reformatting a phone number string in a specific structured way. The input is a string number containing digits, spaces, and dashes. Our task is to first remove all non-digit characters, then partition the digits into blocks of length 3, with special handling for the last few digits: if exactly 4 digits remain, split them into two blocks of 2; if 3 digits remain, a single block of 3; and if 2 digits remain, a single block of 2. The final output should be a string where blocks are separated by dashes, with no block of length 1 allowed.
The constraints specify that number has a length between 2 and 100, contains only digits, spaces, or dashes, and has at least two digits. This ensures that we always have enough digits to form valid blocks and that performance is not a major concern for standard solutions. Important edge cases include strings that are already formatted, strings with consecutive non-digit characters, and strings with exactly 2, 3, or 4 digits remaining at the end.
Approaches
A brute-force approach involves iterating over the string character by character, constructing a cleaned digit string, and then trying every possible way to split it into blocks until we find a valid one. While this would produce the correct result, it is unnecessarily complicated and inefficient for larger inputs.
The key insight for an optimal solution is to first strip all non-digit characters to get a clean sequence of digits. Then, repeatedly take blocks of 3 digits until the remaining digits are 4 or fewer. This guarantees that we handle the special cases of 2, 3, or 4 digits efficiently and ensures no block of length 1 is produced. This approach is linear in time and straightforward to implement.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^2) | O(n) | Constructing all possible block arrangements until a valid one is found |
| Optimal | O(n) | O(n) | Linear pass to clean digits, then linear pass to form blocks according to rules |
Algorithm Walkthrough
- Clean the input: Iterate over the input string
numberand append only digits to a new string or list. This removes spaces and dashes. - Initialize storage for blocks: Create an empty list to hold blocks of digits.
- Form blocks of 3 digits: While the length of the remaining digits is greater than 4, take the first 3 digits as a block, append it to the blocks list, and remove them from the remaining digits.
- Handle the final 2 to 4 digits: After the above step, exactly 2, 3, or 4 digits remain:
- If 4 digits remain, split into two blocks of 2 digits each.
- If 3 digits remain, form one block of 3 digits.
- If 2 digits remain, form one block of 2 digits.
- Join blocks: Use the dash
-character to join all blocks and return the resulting string.
Why it works: By repeatedly taking blocks of 3 digits, we ensure that the final digits are always 2, 3, or 4. The special handling for these last digits guarantees no block of length 1 appears, and the final dash-separated join produces the correctly formatted number.
Python Solution
class Solution:
def reformatNumber(self, number: str) -> str:
digits = [ch for ch in number if ch.isdigit()]
blocks = []
while len(digits) > 4:
blocks.append(''.join(digits[:3]))
digits = digits[3:]
if len(digits) == 4:
blocks.append(''.join(digits[:2]))
blocks.append(''.join(digits[2:]))
else:
blocks.append(''.join(digits))
return '-'.join(blocks)
This implementation first constructs a list of digits by filtering out non-digit characters. It then forms blocks of 3 digits until fewer than 5 digits remain. The remaining digits are handled according to the rules, and the final blocks are joined with dashes to produce the formatted phone number.
Go Solution
func reformatNumber(number string) string {
digits := []byte{}
for i := 0; i < len(number); i++ {
if number[i] >= '0' && number[i] <= '9' {
digits = append(digits, number[i])
}
}
blocks := []string{}
for len(digits) > 4 {
blocks = append(blocks, string(digits[:3]))
digits = digits[3:]
}
if len(digits) == 4 {
blocks = append(blocks, string(digits[:2]))
blocks = append(blocks, string(digits[2:]))
} else {
blocks = append(blocks, string(digits))
}
result := ""
for i, block := range blocks {
if i > 0 {
result += "-"
}
result += block
}
return result
}
In Go, we use a byte slice to store digits. Slices are convenient for removing processed digits and converting to strings. The main logic is identical to Python: process blocks of 3, handle the last 2-4 digits, and join blocks with dashes.
Worked Examples
Example 1: "1-23-45 6"
| Step | Digits Remaining | Blocks Formed |
|---|---|---|
| Initial | 123456 |
[] |
| Take 3 | 456 |
["123"] |
| Final 3 digits | 456 |
["123", "456"] |
| Result | - | "123-456" |
Example 2: "123 4-567"
| Step | Digits Remaining | Blocks Formed |
|---|---|---|
| Initial | 1234567 |
[] |
| Take 3 | 4567 |
["123"] |
| Final 4 digits | 45, 67 |
["123", "45", "67"] |
| Result | - | "123-45-67" |
Example 3: "123 4-5678"
| Step | Digits Remaining | Blocks Formed |
|---|---|---|
| Initial | 12345678 |
[] |
| Take 3 | 45678 |
["123"] |
| Take 3 | 78 |
["123", "456"] |
| Final 2 digits | 78 |
["123", "456", "78"] |
| Result | - | "123-456-78" |
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Linear scan to filter digits and another linear scan to form blocks |
| Space | O(n) | Storage for cleaned digits and final blocks list |
The algorithm is efficient for the constraints, with n ≤ 100.
Test Cases
# Basic examples
assert Solution().reformatNumber("1-23-45 6") == "123-456" # 6 digits
assert Solution().reformatNumber("123 4-567") == "123-45-67" # 7 digits
assert Solution().reformatNumber("123 4-5678") == "123-456-78" # 8 digits
# Edge cases
assert Solution().reformatNumber("12") == "12" # exactly 2 digits
assert Solution().reformatNumber("123") == "123" # exactly 3 digits
assert Solution().reformatNumber("1234") == "12-34" # exactly 4 digits
# All dashes or spaces
assert Solution().reformatNumber("1-2 3-4 5") == "123-45" # mixture of dashes and spaces
# Long string
assert Solution().reformatNumber("123456789012345") == "123-456-789-012-34-5" or similar depending on handling last digits
| Test | Why |
|---|---|
| "1-23-45 6" | Standard 6-digit input |
| "123 4-567" | Remaining 4 digits split into two blocks of 2 |
| "123 4-5678" | Remaining 2 digits form a single block of 2 |
| "12" | Minimum length input, 2 digits |
| "1234" | Edge case of exactly 4 digits |
| "1-2 3-4 5" | Input with mixed non-digit separators |
Edge Cases
The first edge case is a phone number with exactly 2 digits, such as "12". A naive implementation that always tries to form 3-digit blocks could incorrectly produce a block of length 1. Our solution handles this by directly adding remaining digits when ≤ 4 remain.
The second edge case involves exactly 4 remaining digits, like "1234". The algorithm splits these into two 2-digit blocks, ensuring no single-digit blocks occur, conforming to the rules.
The third edge case is inputs with a mix of spaces and dashes, such as "1-2 3-4 5". Filtering out non-digit characters ensures that separators do not interfere with block formation. This guarantees consistent behavior regardless of original formatting.