1805. Number of Different Integers in a String

Description

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 of different integers after performing the replacement operations on word.

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

Example 1:

Input: word = "a123bc34d8ef34"
Output: 3
Explanation: The three different integers are "123", "34", and "8". Notice that "34" is only counted once.

Example 2:

Input: word = "leet1234code234"
Output: 2

Example 3:

Input: word = "a1b01c001"
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.

Solutions

Solution 1: Double Pointers + Simulation

Thinking

We must count distinct integers formed by digit runs, treating leading zeros as the same value. Converting each run to an integer can overflow, because a run may be as long as the whole string.

Two pointers isolate each contiguous digit block, skip leading zeros, and insert the remaining substring (empty when the run is all zeros) into a hash set. The set size is the number of distinct integers, and we never convert a token to a numeric type.

Traverse the string word, find the start and end positions of each integer, cut out this substring, and store it in the hash set \(s\).

After the traversal, return the size of the hash set \(s\).

Note, the integer represented by each substring may be very large, we cannot directly convert it to an integer. Therefore, we can remove the leading zeros of each substring before storing it in the hash set.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the string word.

Python3JavaC++GoTypeScriptRust

class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        s = set()
        i, n = 0, len(word)
        while i < n:
            if word[i].isdigit():
                while i < n and word[i] == '0':
                    i += 1
                j = i
                while j < n and word[j].isdigit():
                    j += 1
                s.add(word[i:j])
                i = j
            i += 1
        return len(s)

class Solution {
    public int numDifferentIntegers(String word) {
        Set<String> s = new HashSet<>();
        int n = word.length();
        for (int i = 0; i < n; ++i) {
            if (Character.isDigit(word.charAt(i))) {
                while (i < n && word.charAt(i) == '0') {
                    ++i;
                }
                int j = i;
                while (j < n && Character.isDigit(word.charAt(j))) {
                    ++j;
                }
                s.add(word.substring(i, j));
                i = j;
            }
        }
        return s.size();
    }
}

class Solution {
public:
    int numDifferentIntegers(string word) {
        unordered_set<string> s;
        int n = word.size();
        for (int i = 0; i < n; ++i) {
            if (isdigit(word[i])) {
                while (i < n && word[i] == '0') ++i;
                int j = i;
                while (j < n && isdigit(word[j])) ++j;
                s.insert(word.substr(i, j - i));
                i = j;
            }
        }
        return s.size();
    }
};

func numDifferentIntegers(word string) int {
    s := map[string]struct{}{}
    n := len(word)
    for i := 0; i < n; i++ {
        if word[i] >= '0' && word[i] <= '9' {
            for i < n && word[i] == '0' {
                i++
            }
            j := i
            for j < n && word[j] >= '0' && word[j] <= '9' {
                j++
            }
            s[word[i:j]] = struct{}{}
            i = j
        }
    }
    return len(s)
}

function numDifferentIntegers(word: string): number {
    return new Set(
        word
            .replace(/\D+/g, ' ')
            .trim()
            .split(' ')
            .filter(v => v !== '')
            .map(v => v.replace(/^0+/g, '')),
    ).size;
}

use std::collections::HashSet;
impl Solution {
    pub fn num_different_integers(word: String) -> i32 {
        let s = word.as_bytes();
        let n = s.len();
        let mut set = HashSet::new();
        let mut i = 0;
        while i < n {
            if s[i] >= b'0' && s[i] <= b'9' {
                let mut j = i;
                while j < n && s[j] >= b'0' && s[j] <= b'9' {
                    j += 1;
                }
                while i < j - 1 && s[i] == b'0' {
                    i += 1;
                }
                set.insert(String::from_utf8(s[i..j].to_vec()).unwrap());
                i = j;
            } else {
                i += 1;
            }
        }
        set.len() as i32
    }
}

1805. Number of Different Integers in a String

Description

Solutions

Solution 1: Double Pointers + Simulation

Comments