algoadvance

Leetcode 1694. Reformat Phone Number

Problem Statement:

Given a string number that consists of digits, spaces, and dashes, you need to reformat the string so that each group contains exactly three digits, except for the last group which could consider the remaining two digits. If there are exactly four digits left, they should be split into two groups of two digits. You should return the reformatted string.

Example:

• Input: number = "1-23-45 6"

• Output: "123-456"

• Input: number = "123 4-567"
• Output: "123-45-67"

Clarifying Questions:

1. Can the input number have leading or trailing spaces?
   • We assume no leading or trailing spaces unless stated otherwise.
2. What is the maximum length of the number string?
   • This typically would follow the constraint limits provided in LeetCode, but we can assume a reasonable length for the simplicity of this example.
3. How should we handle invalid characters or empty strings?
   • We assume that the input string will only contain valid digits, spaces, and dashes as per the problem statement.

Strategy:

1. Remove Non-numeric Characters:
   • Strip out any spaces and dashes from the string to get a contiguous sequence of digits.
2. Reformat String:
   • Traverse the cleaned string and insert dashes appropriately:
     • Add groups of 3 digits until fewer than 4 digits are left.
     • If exactly 4 digits are left, split into two groups of 2 digits.
3. Return Result:
   • Construct the formatted number from the processed groups.

Code:

Here is the C++ implementation of the above strategy:

#include <iostream>
#include <string>

std::string reformatNumber(std::string number) {
    // Step 1: Remove non-numeric characters
    std::string digits;
    for (char c : number) {
        if (isdigit(c)) {
            digits += c;
        }
    }

    // Step 2: Reformat the string
    std::string result;
    int n = digits.size();
    int i = 0;
    
    while (n > 0) {
        if (n > 4) {
            result += digits.substr(i, 3) + "-";
            i += 3;
            n -= 3;
        } else if (n == 4) {
            result += digits.substr(i, 2) + "-" + digits.substr(i + 2, 2);
            break;
        } else {
            result += digits.substr(i, n);
            break;
        }
    }
    
    return result;
}

// Test cases
int main() {
    std::string number1 = "1-23-45 6";
    std::string number2 = "123 4-567";
    std::string number3 = "123 4-5678";
    std::string number4 = "12";
    std::string number5 = "--17-5 229 35-39475 ";

    std::cout << reformatNumber(number1) << std::endl; // Output: "123-456"
    std::cout << reformatNumber(number2) << std::endl; // Output: "123-45-67"
    std::cout << reformatNumber(number3) << std::endl; // Output: "123-456-78"
    std::cout << reformatNumber(number4) << std::endl; // Output: "12"
    std::cout << reformatNumber(number5) << std::endl; // Output: "175-229-353-947-5"

    return 0;
}

Time Complexity:

• Time Complexity: O(n)
  • Where n is the length of the input string number. This is because we are processing each character in the string twice: once to remove non-numeric characters and once more to reformat the string.
• Space Complexity: O(n)
  • Additional space is used to store the digits and the resulting reformatted string.

This solution should handle the typical constraints and provide the desired phone number reformatting efficiently.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?