Leetcode – Reformat Phone Number Solution

Spread the love

String manipulation and formatting are common tasks in software development. In coding interviews, questions about strings serve as a useful gauge for understanding your grasp of programming basics. The “Reformat Phone Number” problem on Leetcode is one such question. Although simple at first glance, this problem provides an excellent opportunity to dive deeper into string manipulation techniques in Python.In this comprehensive guide, we will explore multiple approaches for solving the problem, including their pros and cons. Additionally, we’ll consider time and space complexities.

Problem Statement

Given a phone number string that contains dashes, spaces, or no separators, reformat the phone number into a string that includes dashes as the separator, with a maximum of three characters between each dash.

Example:

Input: "123 4-567"
Output: "123-45-67"

Basic Approach: String Cleaning and Rebuilding

The initial approach is straightforward:

  1. Remove all non-digit characters from the input string.
  2. Reconstruct the phone number with dashes according to the required format.

Python Code

def reformatNumber(number):
    cleaned = ''.join(filter(str.isdigit, number))
    i, n = 0, len(cleaned)
    parts = []
    while i < n:
        if n - i > 4:
            parts.append(cleaned[i:i+3])
            i += 3
        elif n - i == 4:
            parts.append(cleaned[i:i+2])
            i += 2
        else:
            parts.append(cleaned[i:i+3])
            i += 3
    return '-'.join(parts)

Time Complexity

The time complexity for this approach is O(n), where n is the length of the input string.

Optimized Approach: StringBuilder

In Python, string concatenation can be costly when done repeatedly, especially in a loop. Instead, you can collect all parts into a list and use the join() method for a more efficient operation.

Python Code

def reformatNumber(number):
    cleaned = ''.join(filter(str.isdigit, number))
    i, n = 0, len(cleaned)
    parts = []
    while i < n:
        chunk_size = 4 if n - i == 4 else 3 if n - i > 4 else n - i
        parts.append(cleaned[i:i+chunk_size])
        i += chunk_size
    return '-'.join(parts)

Time Complexity

The time complexity remains O(n), but the StringBuilder approach generally runs faster in practice due to more efficient string concatenation.

Conclusion

The “Reformat Phone Number” problem might not be the most challenging problem out there, but it offers a good exercise in basic string manipulation techniques. From filtering out unwanted characters to reconstructing a string based on specific conditions, this problem encapsulates a lot of what you’d commonly do in a text-processing task.

Leave a Reply