Leetcode – Number of Different Integers in a String Solution

Spread the love

The “Number of Different Integers in a String” problem on Leetcode is an interesting problem that combines string manipulation and integer handling. It tests your ability to parse strings, recognize integers, and apply basic data structures like sets to solve problems efficiently. In this comprehensive article, we will dive into multiple approaches to solve the problem, evaluate their time and space complexities, and analyze the underlying principles of each method.

Problem Statement

You are given a string word that consists of digits and lowercase English letters. Your task is to return the number of different integers that can be represented by substrings in the given string.

Examples

Input: word = "a123bc34d8ef34"
Output: 3

Input: word = "leet1234code234"
Output: 2

Input: word = "a1b01c001"
Output: 1

Approach 1: Simple String Traversal

One straightforward way to solve the problem is by using simple string traversal to parse the integers and add them to a set to avoid duplicates.

Algorithm Steps:

  1. Initialize an empty set unique_numbers and a temporary string current_number.
  2. Loop through each character in the string.
  3. If the character is a digit, append it to current_number.
  4. If it’s not a digit and current_number is not empty, add the integer form of current_number to unique_numbers and reset current_number.
  5. Finally, return the length of unique_numbers.

Python Code:

def numDifferentIntegers(word: str) -> int:
    unique_numbers = set()
    current_number = ""
    for char in word:
        if char.isdigit():
            current_number += char
        else:
            if current_number:
                unique_numbers.add(int(current_number))
            current_number = ""
    if current_number:
        unique_numbers.add(int(current_number))
    return len(unique_numbers)

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the string.
  • Space Complexity: O(n) due to the set and temporary string.

Approach 2: Using Regular Expressions

Python’s re library can be used to simplify the process of extracting integers from the string.

Algorithm Steps:

  1. Use re.findall to find all sequences of digits in the string.
  2. Convert these sequences to integers and add them to a set.
  3. Return the length of the set.

Python Code:

import re

def numDifferentIntegers(word: str) -> int:
    numbers = set(map(int, re.findall(r'\d+', word)))
    return len(numbers)

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the string.
  • Space Complexity: O(n), due to the set and list of sequences.

Approach 3: String Splitting and Enumeration (Optional)

This approach involves manually splitting the string into a list by digits and using enumeration to parse integers.

Algorithm Steps:

  1. Replace all non-digit characters with a space.
  2. Split the string into a list using the space as a separator.
  3. Convert the elements to integers and add them to a set.
  4. Return the length of the set.

Python Code:

def numDifferentIntegers(word: str) -> int:
    for char in word:
        if not char.isdigit():
            word = word.replace(char, ' ')
    unique_numbers = set(map(int, word.split()))
    return len(unique_numbers)

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the string.
  • Space Complexity: O(n), due to the set and list.

Conclusion

The “Number of Different Integers in a String” problem offers an intriguing blend of string parsing and set manipulation. Although all the approaches yield similar time and space complexities, the techniques involved differ. The simple string traversal approach provides a good understanding of the basics, whereas the regular expression method offers a more advanced yet simplified way to solve the problem. Finally, the string splitting approach gives yet another perspective on how to manipulate and parse strings.

Leave a Reply