Reformat Phone Number

Difficulty: Easy | Acceptance: 67.70% | Paid: No Topics: String

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. Specifically, the digits should be grouped in blocks of length 3, separated by dashes, except possibly for the last block, which could be of length 2 or 3, but not 1. If the last block has length 4, it should be split into two blocks of length 2.

Return the reformatted phone number.

• Examples
• Constraints
• String Manipulation
• Queue-based Approach
• Modular Arithmetic

Examples

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 <= 100
number consists of digits, spaces ' ', and/or dashes '-'.

String Manipulation

Intuition Clean the input string by removing non-digit characters, then iterate through the cleaned string building groups of 3 digits, with special handling when 4 digits remain.

Steps

• Remove all non-digit characters from the input string
• Iterate through the cleaned string with a pointer
• When 4 digits remain, split into two groups of 2
• When 2 or 3 digits remain, take all remaining digits
• Otherwise, take groups of 3 digits
• Join all groups with dashes

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

Complexity

• Time: O(n) where n is the length of the input string
• Space: O(n) for storing the cleaned string and result
• Notes: Simple and intuitive approach with clear logic flow

Queue-based Approach

Intuition Use a queue to store digits and process them in groups, taking 3 at a time until 4 or fewer remain, then handle the special cases.

Steps

• Create a queue containing only digit characters
• While queue has more than 4 elements, dequeue 3 and add as a group
• Handle remaining 2, 3, or 4 digits appropriately
• Join all groups with dashes

from collections import deque

class Solution:
    def reformatNumber(self, number: str) -> str:
        queue = deque(c for c in number if c.isdigit())
        
        result = []
        
        while len(queue) > 4:
            result.append(''.join([queue.popleft() for _ in range(3)]))
        
        remaining = ''.join(queue)
        if len(remaining) == 4:
            result.append(remaining[:2])
            result.append(remaining[2:])
        else:
            result.append(remaining)
        
        return '-'.join(result)

Complexity

• Time: O(n) where n is the length of the input string
• Space: O(n) for the queue and result storage
• Notes: Uses queue semantics which naturally model the problem of processing digits sequentially

Modular Arithmetic

Intuition Use the remainder when dividing by 3 to determine the optimal grouping strategy upfront, then build the result accordingly.

Steps

• Clean the input string to extract only digits
• Calculate n % 3 to determine the first group size
• If remainder is 0, first group is 3; if 1, first group is 4 (split as 2-2); if 2, first group is 2
• Process the first group with special handling for size 4
• Process remaining digits in groups of 3
• Join all groups with dashes

class Solution:
    def reformatNumber(self, number: str) -> str:
        cleaned = ''.join(c for c in number if c.isdigit())
        n = len(cleaned)
        
        remainder = n % 3
        if remainder == 0:
            first_group = 3
        elif remainder == 1:
            first_group = 4
        else:
            first_group = 2
        
        result = []
        i = 0
        
        if first_group == 4:
            result.append(cleaned[i:i+2])
            result.append(cleaned[i+2:i+4])
            i += 4
        else:
            result.append(cleaned[i:i+first_group])
            i += first_group
        
        while i < n:
            result.append(cleaned[i:i+3])
            i += 3
        
        return '-'.join(result)

Complexity

• Time: O(n) where n is the length of the input string
• Space: O(n) for storing the cleaned string and result
• Notes: Mathematical approach that determines grouping strategy upfront using modular arithmetic