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:
- Replace all non-digit characters with spaces and split the string using spaces.
- Iterate through the resulting list, get rid of any leading zeros, and track unique integers using a set.
- Return the size of the set.
Let's see how this approach works on our example:
1word = "a123bc34d8ef34"
-
Replace non-digit characters and split:
1" 123 34 8 34".split() => ["123", "34", "8", "34"]
-
Iterate through the list and add unique integers to a set:
1{123, 34, 8}
-
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.