Problem

You are given a string word that consists of digits and lowercase English letters.

You will replace every non-digit character with a space. For example, "a123bc34d8ef34" will become " 123 34 8 34". Notice that you are left with some integers that are separated by at least one space: "123", "34", "8", and "34".

Return _the number ofdifferent integers after performing the replacement operations on _word.

Two integers are considered different if their decimal representations without any leading zeros are different.

Examples

Example 1

1
2
3
4
5
6
7


    
    
    Input: word = "a _123_ bc _34_ d _8_ ef _34_ "
    Output: 3
    Explanation: The three different integers are "123", "34", and "8". Notice that "34" is only counted once.

Example 2

1
2
3
4
5
6


    
    
    Input: word = "leet _1234_ code _234_ "
    Output: 2

Example 3

1
2
3
4
5
6
7
8


    
    
    Input: word = "a _1_ b _01_ c _001_ "
    Output: 1
    Explanation: The three integers "1", "01", and "001" all represent the same integer because
    the leading zeros are ignored when comparing their decimal values.

Constraints

  • 1 <= word.length <= 1000
  • word consists of digits and lowercase English letters.

Solution

Method 1 – String Parsing and Set

Intuition

Replace all non-digit characters with spaces, split the string, and collect all unique integers (ignoring leading zeros) in a set.

Approach

  1. Replace all non-digit characters with spaces.
  2. Split the string into tokens, strip leading zeros, and add to a set.
  3. Return the size of the set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <string>
#include <set>
using namespace std;
class Solution {
public:
    int numDifferentIntegers(string word) {
        set<string> s;
        int n = word.size();
        for (int i = 0; i < n;) {
            if (isdigit(word[i])) {
                int j = i;
                while (j < n && isdigit(word[j])) ++j;
                string num = word.substr(i, j-i);
                while (num.size() > 1 && num[0] == '0') num.erase(0,1);
                s.insert(num);
                i = j;
            } else ++i;
        }
        return s.size();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import "unicode"
func numDifferentIntegers(word string) int {
    s := map[string]struct{}{}
    n := len(word)
    for i := 0; i < n; {
        if unicode.IsDigit(rune(word[i])) {
            j := i
            for j < n && unicode.IsDigit(rune(word[j])) { j++ }
            num := word[i:j]
            for len(num) > 1 && num[0] == '0' { num = num[1:] }
            s[num] = struct{}{}
            i = j
        } else { i++ }
    }
    return len(s)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import java.util.*;
class Solution {
    public int numDifferentIntegers(String word) {
        Set<String> set = new HashSet<>();
        int n = word.length();
        for (int i = 0; i < n;) {
            if (Character.isDigit(word.charAt(i))) {
                int j = i;
                while (j < n && Character.isDigit(word.charAt(j))) j++;
                String num = word.substring(i, j);
                while (num.length() > 1 && num.charAt(0) == '0') num = num.substring(1);
                set.add(num);
                i = j;
            } else i++;
        }
        return set.size();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun numDifferentIntegers(word: String): Int {
        val set = mutableSetOf<String>()
        var i = 0
        while (i < word.length) {
            if (word[i].isDigit()) {
                var j = i
                while (j < word.length && word[j].isDigit()) j++
                var num = word.substring(i, j)
                while (num.length > 1 && num[0] == '0') num = num.substring(1)
                set.add(num)
                i = j
            } else i++
        }
        return set.size
    }
}
1
2
3
4
5

class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        import re
        nums = re.findall(r'\d+', word)
        return len(set(num.lstrip('0') or '0' for num in nums))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

use std::collections::HashSet;
impl Solution {
    pub fn num_different_integers(word: String) -> i32 {
        let mut set = HashSet::new();
        let mut i = 0;
        let n = word.len();
        let bytes = word.as_bytes();
        while i < n {
            if bytes[i].is_ascii_digit() {
                let mut j = i;
                while j < n && bytes[j].is_ascii_digit() { j += 1; }
                let mut num = &word[i..j];
                while num.len() > 1 && num.starts_with('0') { num = &num[1..]; }
                set.insert(num.to_string());
                i = j;
            } else { i += 1; }
        }
        set.len() as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

function numDifferentIntegers(word: string): number {
    const set = new Set<string>();
    let i = 0;
    while (i < word.length) {
        if (/[0-9]/.test(word[i])) {
            let j = i;
            while (j < word.length && /[0-9]/.test(word[j])) j++;
            let num = word.slice(i, j);
            while (num.length > 1 && num[0] === '0') num = num.slice(1);
            set.add(num);
            i = j;
        } else i++;
    }
    return set.size;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)