Problem

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. Firstly, 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:

  • 2 digits: A single block of length 2.
  • 3 digits: A single block of length 3.
  • 4 digits: Two blocks of length 2 each.

The blocks are then joined by dashes. Notice that the reformatting process should never produce any blocks of length 1 and produce at most two blocks of length 2.

Return the phone number after formatting.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4
5
6

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

1
2
3
4
5
6
7

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 and the characters '-' and ' '.
  • There are at least two digits in number.

Solution

Method 1 – Greedy Grouping

Intuition

Remove all non-digit characters, then greedily group digits into blocks of 3 until 4 or fewer remain. The last 2 or 4 digits are handled specially to avoid blocks of length 1.

Approach

  1. Remove all spaces and dashes from the input.
  2. While the number of digits left is more than 4, take the next 3 digits as a block.
  3. For the last 2, 3, or 4 digits, group as per the rules:
    • 2 digits: one block of 2
    • 3 digits: one block of 3
    • 4 digits: two blocks of 2
  4. Join all blocks with dashes and return.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    string reformatNumber(string number) {
        string digits;
        for (char c : number) if (isdigit(c)) digits += c;
        vector<string> blocks;
        int i = 0, n = digits.size();
        while (n - i > 4) {
            blocks.push_back(digits.substr(i, 3));
            i += 3;
        }
        if (n - i == 4) {
            blocks.push_back(digits.substr(i, 2));
            blocks.push_back(digits.substr(i+2, 2));
        } else if (n - i == 3) {
            blocks.push_back(digits.substr(i, 3));
        } else if (n - i == 2) {
            blocks.push_back(digits.substr(i, 2));
        }
        return join(blocks, "-");
    }
private:
    string join(const vector<string>& v, const string& sep) {
        string res;
        for (int i = 0; i < v.size(); ++i) {
            if (i) res += sep;
            res += v[i];
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import "strings"
func reformatNumber(number string) string {
    digits := make([]byte, 0, len(number))
    for i := 0; i < len(number); i++ {
        if number[i] >= '0' && number[i] <= '9' {
            digits = append(digits, number[i])
        }
    }
    blocks := []string{}
    i := 0
    n := len(digits)
    for n-i > 4 {
        blocks = append(blocks, string(digits[i:i+3]))
        i += 3
    }
    if n-i == 4 {
        blocks = append(blocks, string(digits[i:i+2]))
        blocks = append(blocks, string(digits[i+2:i+4]))
    } else if n-i == 3 {
        blocks = append(blocks, string(digits[i:i+3]))
    } else if n-i == 2 {
        blocks = append(blocks, string(digits[i:i+2]))
    }
    return strings.Join(blocks, "-")
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class Solution {
    public String reformatNumber(String number) {
        StringBuilder digits = new StringBuilder();
        for (char c : number.toCharArray()) if (Character.isDigit(c)) digits.append(c);
        List<String> blocks = new ArrayList<>();
        int i = 0, n = digits.length();
        while (n - i > 4) {
            blocks.add(digits.substring(i, i+3));
            i += 3;
        }
        if (n - i == 4) {
            blocks.add(digits.substring(i, i+2));
            blocks.add(digits.substring(i+2, i+4));
        } else if (n - i == 3) {
            blocks.add(digits.substring(i, i+3));
        } else if (n - i == 2) {
            blocks.add(digits.substring(i, i+2));
        }
        return String.join("-", blocks);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun reformatNumber(number: String): String {
        val digits = number.filter { it.isDigit() }
        val blocks = mutableListOf<String>()
        var i = 0
        val n = digits.length
        while (n - i > 4) {
            blocks.add(digits.substring(i, i+3))
            i += 3
        }
        if (n - i == 4) {
            blocks.add(digits.substring(i, i+2))
            blocks.add(digits.substring(i+2, i+4))
        } else if (n - i == 3) {
            blocks.add(digits.substring(i, i+3))
        } else if (n - i == 2) {
            blocks.add(digits.substring(i, i+2))
        }
        return blocks.joinToString("-")
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def reformatNumber(self, number: str) -> str:
        digits = [c for c in number if c.isdigit()]
        ans = []
        i, n = 0, len(digits)
        while n - i > 4:
            ans.append(''.join(digits[i:i+3]))
            i += 3
        if n - i == 4:
            ans.append(''.join(digits[i:i+2]))
            ans.append(''.join(digits[i+2:i+4]))
        elif n - i == 3:
            ans.append(''.join(digits[i:i+3]))
        elif n - i == 2:
            ans.append(''.join(digits[i:i+2]))
        return '-'.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

impl Solution {
    pub fn reformat_number(number: String) -> String {
        let digits: Vec<char> = number.chars().filter(|c| c.is_ascii_digit()).collect();
        let mut ans = Vec::new();
        let mut i = 0;
        let n = digits.len();
        while n - i > 4 {
            ans.push(digits[i..i+3].iter().collect::<String>());
            i += 3;
        }
        if n - i == 4 {
            ans.push(digits[i..i+2].iter().collect());
            ans.push(digits[i+2..i+4].iter().collect());
        } else if n - i == 3 {
            ans.push(digits[i..i+3].iter().collect());
        } else if n - i == 2 {
            ans.push(digits[i..i+2].iter().collect());
        }
        ans.join("-")
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    reformatNumber(number: string): string {
        const digits = Array.from(number).filter(c => c >= '0' && c <= '9');
        const ans: string[] = [];
        let i = 0, n = digits.length;
        while (n - i > 4) {
            ans.push(digits.slice(i, i+3).join(''));
            i += 3;
        }
        if (n - i === 4) {
            ans.push(digits.slice(i, i+2).join(''));
            ans.push(digits.slice(i+2, i+4).join(''));
        } else if (n - i === 3) {
            ans.push(digits.slice(i, i+3).join(''));
        } else if (n - i === 2) {
            ans.push(digits.slice(i, i+2).join(''));
        }
        return ans.join('-');
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the input string, since we scan and build the result in linear time.
  • 🧺 Space complexity: O(n), for storing the digits and the result.