algoadvance

The problem statement in LeetCode is as follows:

You are given a phone number as a string number. number consists of digits, spaces ' ', and/or dashes '-'.

You want to reformat the phone number in a certain manner. Firstly, you should 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:

Finally, you reformat the digits into a string by joining the blocks with dashes.

Given a string number, return the reformatted phone number.

Example

  1. Input: number = “1-23-45 6”
    • Output: “123-456”
  2. Input: number = “123 4-567”
    • Output: “123-45-67”
  3. Input: number = “123 4-5678”
    • Output: “123-456-78”

Constraints

Clarifying Questions

  1. Q: Can the input number be empty or null?
    • A: No, according to the constraints, the input number will have a length between 2 and 100 inclusive.
  2. Q: Are there any other characters except digits, spaces, and dashes?
    • A: No, the input will only consist of digits, spaces, and dashes.
  3. Q: Are the input digits guaranteed to form a valid phone number?
    • A: The constraints guarantee that there will be at least two digits, and the given rules will always produce a valid phone number reformat.

Strategy

  1. Remove all spaces and dashes from the input string to get a continuous sequence of digits.
  2. Initialize an empty list to store the resulting groups of digits.
  3. While the length of the sequence is more than 4:
    • Take the first 3 digits and append them to the result list.
  4. Handle the remaining digits based on their count:
    • If there are exactly 4 digits left, split them into two groups of 2 digits each.
    • If there are 3 or fewer digits left, append them as a single group.
  5. Join the groups with dashes and return the reformatted phone number.

Code

def reformatNumber(number: str) -> str:
    # Remove dashes and spaces
    digits = ''.join(ch for ch in number if ch.isdigit())
    
    result = []
    i = 0
    n = len(digits)
    
    # Process the digits
    while i < n:
        if n - i > 4:
            result.append(digits[i:i+3])
            i += 3
        else:
            if n - i == 4:
                result.append(digits[i:i+2])
                result.append(digits[i+2:i+4])
            else:
                result.append(digits[i:])
            
            break
    
    return '-'.join(result)

# Example Usage
print(reformatNumber("1-23-45 6"))       # Output: "123-456"
print(reformatNumber("123 4-567"))        # Output: "123-45-67"
print(reformatNumber("123 4-5678"))       # Output: "123-456-78"

Time Complexity

The time complexity for this solution is (O(n)), where (n) is the length of the input string. This is because we pass through the string a couple of times: once to filter out non-digit characters and again to split the digits into groups.

The space complexity is also (O(n)) due to the storage requirements for the digit characters and the resulting blocks.

This ensures the solution is efficient and suitable for the input size constraints given in the problem statement.

Try our interview co-pilot at AlgoAdvance.com