Number of Different Integers in a String — LeetCode 1805 Python Solution

The 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.

Example

Input

word = "a123bc34d8ef34"

Output

3

Explanation

The three different integers are "123", "34", and "8". Notice that "34" is only counted once.

Python solution

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)

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1805. Number of Different Integers in a String is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems