Leetcode 1805. Number of Different Integers in a String Solution

Problem Description

In this problem, you are given a string word that consists of digits and lowercase English letters. The goal is to replace every non-digit character with a space and then find the number of different integers in the modified string. Two integers are considered different if their decimal representations without any leading zeros are different.

Let's walk through an example:

Example:

1Input: word = "a123bc34d8ef34"
2Output: 3

In this example, after replacing non-digit characters with spaces, we have the following string:

1" 123  34 8  34"

Now, we can extract the integers present in this string, which are "123", "34", "8", and "34". Notice that "34" appears twice, but we only count it once since we're interested in the number of different integers. Hence, the answer is 3 because there are three unique integers: "123", "34", and "8".

Approach

This problem can be solved by following these steps:

  1. Replace all non-digit characters with spaces and split the string using spaces.
  2. Iterate through the resulting list, get rid of any leading zeros, and track unique integers using a set.
  3. Return the size of the set.

Let's see how this approach works on our example:

1word = "a123bc34d8ef34"
  1. Replace non-digit characters and split:

    1" 123  34 8  34".split() => ["123", "34", "8", "34"]
  2. Iterate through the list and add unique integers to a set:

    1{123, 34, 8}
  3. Return the size of the set:

    13

Now let's implement this approach in different programming languages.

Python Solution

1class Solution:
2    def numDifferentIntegers(self, word: str) -> int:
3        # Replace non-digit characters with spaces and split the string
4        nums = word.translate(str.maketrans('abcdefghijklmnopqrstuvwxyz', ' ' * 26)).split()
5        
6        # Use a set to store unique integers (ignoring leading zeros)
7        unique_ints = set(int(num) for num in nums)
8        
9        return len(unique_ints)

Java Solution

1import java.util.HashSet;
2import java.util.Set;
3
4class Solution {
5    public int numDifferentIntegers(String word) {
6        String noLetters = word.replaceAll("[a-z]", " ");
7        String[] nums = noLetters.split("\\s+");
8        Set<Integer> uniqueInts = new HashSet<>();
9
10        for (String num : nums) {
11            if (!num.isEmpty()) {
12                uniqueInts.add(Integer.parseInt(num));
13            }
14        }
15
16        return uniqueInts.size();
17    }
18}

JavaScript Solution

1class Solution {
2    numDifferentIntegers(word) {
3        const nums = word.split(/[a-z]/).filter(e => e !== '');
4        const uniqueInts = new Set(nums.map(num => parseInt(num, 10)));
5
6        return uniqueInts.size;
7    }
8}

C++ Solution

1#include <set>
2#include <sstream>
3#include <algorithm>
4
5class Solution {
6public:
7    int numDifferentIntegers(std::string word) {
8        std::set<int> uniqueInts;
9        std::for_each(word.begin(), word.end(), [](char& c) {
10            if ('a' <= c && c <= 'z') c = ' ';
11        });
12
13        std::istringstream iss(word);
14        int num;
15        while (iss >> num) {
16            uniqueInts.insert(num);
17        }
18
19        return uniqueInts.size();
20    }
21};

C# Solution

1using System.Collections.Generic;
2using System.Text.RegularExpressions;
3
4public class Solution {
5    public int NumDifferentIntegers(string word) {
6        string[] nums = Regex.Split(word, "[a-z]+");
7        HashSet<int> uniqueInts = new HashSet<int>();
8        
9        foreach (string num in nums) {
10            if (num != "") {
11                uniqueInts.Add(int.Parse(num));
12            }
13        }
14        
15        return uniqueInts.Count;
16    }
17}

Summary

In this article, we provided solutions for the given problem statement in five popular programming languages - Python, Java, JavaScript, C++, and C#. The main idea behind the implementations is to remove all non-digit characters by replacing them with spaces, then extract the integers present, and count the unique integers found. The solutions use sets to store unique integers efficiently, taking into account that sets do not allow duplicate entries.