Reformat Phone Number
EasyPrompt
You are given a phone number as a string number. number consists of digits, spaces ' ', and/or dashes '-'.
You would like to reformat the phone number in a certain manner. Firstly, remove all spaces and dashes. Then, group the digits from left to right into blocks of length 3 until there are 4 or fewer digits. The final digits are then grouped as follows:
- 2 digits: A single block of length 2.
- 3 digits: A single block of length 3.
- 4 digits: Two blocks of length 2 each.
The blocks are then joined by dashes. Notice that the reformatting process should never produce any blocks of length 1 and produce at most two blocks of length 2.
Return the phone number after formatting.
Example 1:
Input: number = "1-23-45 6"
Output: "123-456"
Explanation: The digits are "123456".
Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123".
Step 2: There are 3 digits remaining, so put them in a single block of length 3. The 2nd block is "456".
Joining the blocks gives "123-456".Example 2:
Input: number = "123 4-567"
Output: "123-45-67"
Explanation: The digits are "1234567".
Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123".
Step 2: There are 4 digits left, so split them into two blocks of length 2. The blocks are "45" and "67".
Joining the blocks gives "123-45-67".Example 3:
Input: number = "123 4-5678"
Output: "123-456-78"
Explanation: The digits are "12345678".
Step 1: The 1st block is "123".
Step 2: The 2nd block is "456".
Step 3: There are 2 digits left, so put them in a single block of length 2. The 3rd block is "78".
Joining the blocks gives "123-456-78".
Constraints:
2 <= number.length <= 100numberconsists of digits and the characters'-'and' '.- There are at least two digits in
number.
Approaches
2 approaches with complexity analysis and trade-offs.
This is a straightforward, brute-force approach that directly translates the problem's requirements into code. It first filters the input string to get only the digits and then formats this new string of digits. The main drawback is its use of repeated string concatenation in a loop, which is known to be inefficient in Java because strings are immutable. Each concatenation creates a new string object, leading to quadratic time complexity.
Algorithm
- Initialize an empty string
digitsOnly. - Iterate through each character of the input
numberstring. - If the character is a digit, append it to
digitsOnlyusing the+operator (digitsOnly += character). - After collecting all digits, initialize another empty string
result. - Use an index
ito iterate throughdigitsOnly. - While the number of remaining digits is more than 4, append a block of 3 digits to
resultfollowed by a dash, using the+operator. Increment the indexiby 3. - Once 4 or fewer digits remain, handle them based on the rules:
- If 4 digits remain, append two blocks of 2, separated by a dash.
- If 2 or 3 digits remain, append them as a single block.
- Return the final
resultstring.
Walkthrough
The process is split into two phases. First, we build a new string containing only the digits from the input. We do this by iterating through the input and appending digits to a string variable. This is inefficient because each += operation on a string creates a new string and copies the content of the old string and the new character.
Second, we build the final formatted string, again using string concatenation. We take blocks of three digits as long as more than four digits are left. The final 2, 3, or 4 digits are handled as a special case.
class Solution { public String reformatNumber(String number) { // Step 1: Filter out non-digits using string concatenation String digitsOnly = ""; for (char c : number.toCharArray()) { if (Character.isDigit(c)) { digitsOnly += c; } } // Step 2: Format the digits string using string concatenation String result = ""; int n = digitsOnly.length(); int i = 0; while (n - i > 4) { result += digitsOnly.substring(i, i + 3); result += "-"; i += 3; } // Handle the last group of digits int remaining = n - i; if (remaining == 4) { result += digitsOnly.substring(i, i + 2); result += "-"; result += digitsOnly.substring(i + 2, i + 4); } else { // remaining is 2 or 3 result += digitsOnly.substring(i, n); } return result; }}Complexity
Time
O(L^2), where L is the length of the input string. If N is the number of digits, the filtering step is O(L * N) and the formatting step is O(N^2) because string concatenation in a loop takes time proportional to the lengths of the strings being joined.
Space
O(N), where N is the number of digits in the input. This space is used to store the `digitsOnly` string and the `result` string. Many more temporary strings are created but are garbage collected.
Trade-offs
Pros
Simple to understand and implement.
The logic directly follows the problem description.
Cons
Highly inefficient in terms of time complexity due to the nature of string concatenation in Java.
Creates a large number of temporary, intermediate string objects, leading to increased work for the garbage collector.
Solutions
Solution
class Solution {public String reformatNumber(String number) { number = number.replace("-", "").replace(" ", ""); int n = number.length(); List<String> ans = new ArrayList<>(); for (int i = 0; i < n / 3; ++i) { ans.add(number.substring(i * 3, i * 3 + 3)); } if (n % 3 == 1) { ans.set(ans.size() - 1, ans.get(ans.size() - 1).substring(0, 2)); ans.add(number.substring(n - 2)); } else if (n % 3 == 2) { ans.add(number.substring(n - 2)); } return String.join("-", ans); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.