algoadvance

Leetcode 1694. Reformat Phone Number

Problem Statement

You are given a phone number in the form of a string number. number consists of digits, spaces ' ', and/or dashes '-'. You want 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 only 4 or fewer digits are left. After that, the reformatting is done as follows:

Return the phone number after reformatting.

Clarifying Questions

  1. What is the maximum length of the phone number string?
    • The problem does not specify, but we can assume it to be reasonably large to fit within typical phone number scenarios.
  2. Are there any other characters we need to consider apart from spaces and dashes?
    • No, only digits, spaces, and dashes are considered.
  3. Should we handle invalid inputs or assume that input is always valid as per the problem description?
    • We can assume the input is always formatted as described in the problem.

Strategy

  1. Remove non-digit characters: We will first remove all spaces ' ' and dashes '-' from the string.
  2. Reformat the digits into groups:
    • If the number of remaining digits is more than 4, group them into chunks of 3.
    • If we have exactly 4 digits remaining, split them into two groups of 2.
  3. Join the groups with dashes and return the result.

Code

public class Solution {
    public String reformatNumber(String number) {
        // Step 1: Remove spaces and dashes
        StringBuilder digits = new StringBuilder();
        for (char ch : number.toCharArray()) {
            if (Character.isDigit(ch)) {
                digits.append(ch);
            }
        }
        
        // Step 2: Reformat digits into blocks of length 3 or 2
        int length = digits.length();
        StringBuilder result = new StringBuilder();
        int i = 0;
        
        // Process chunks of 3 until the remaining characters are handled
        while (length - i > 4) {
            result.append(digits.substring(i, i + 3));
            result.append("-");
            i += 3;
        }
        
        // Handle the last 4 or fewer characters
        if (length - i == 4) {
            result.append(digits.substring(i, i + 2));
            result.append("-");
            result.append(digits.substring(i + 2));
        } else {
            result.append(digits.substring(i));
        }
        
        return result.toString();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.reformatNumber("1-23-45 6"));       // Output: "123-456"
        System.out.println(sol.reformatNumber("123 4-567"));       // Output: "123-45-67"
        System.out.println(sol.reformatNumber("123 4-5678"));      // Output: "123-456-78"
        System.out.println(sol.reformatNumber("12"));              // Output: "12"
        System.out.println(sol.reformatNumber("--17-5 229 35-39475 ")); // Output: "175-229-353-94-75"
    }
}

Time Complexity

The time complexity of this solution is O(n) where n is the length of the input string number. This is because:

This approach is efficient and runs in linear time with respect to the length of the input.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI