1805. Number of Different Integers in a String

Approach 1: Straightforward

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  int numDifferentIntegers(string word) {
    unordered_set<string> nums;
    string curr;

    for (const char c : word)
      if (isdigit(c)) {
        curr += c;
      } else if (curr.length() > 0) {
        nums.insert(removeLeadingZeros(curr));
        curr = "";
      }

    if (curr.length() > 0)
      nums.insert(removeLeadingZeros(curr));
    return nums.size();
  }

 private:
  string removeLeadingZeros(const string& s) {
    const int index = s.find_first_not_of('0');
    return index == string::npos ? "0" : s.substr(index);
  }
};

class Solution {
  public int numDifferentIntegers(String word) {
    HashSet<String> nums = new HashSet<>();
    StringBuilder sb = new StringBuilder();

    for (final char c : word.toCharArray())
      if (Character.isDigit(c)) {
        sb.append(c);
      } else if (sb.length() > 0) {
        nums.add(removeLeadingZeros(sb.toString()));
        sb = new StringBuilder();
      }

    if (sb.length() > 0)
      nums.add(removeLeadingZeros(sb.toString()));
    return nums.size();
  }

  private String removeLeadingZeros(final String s) {
    int index = 0;
    while (index < s.length() && s.charAt(index) == '0')
      ++index;
    return index == s.length() ? "0" : s.substring(index);
  }
}

class Solution:
  def numDifferentIntegers(self, word: str) -> int:
    nums = set()
    curr = []

    for c in word:
      if c.isdigit():
        curr.append(c)
      elif curr:
        nums.add(''.join(self._removeLeadingZeros(curr)))
        curr = []

    if curr:
      nums.add(''.join(self._removeLeadingZeros(curr)))

    return len(nums)

  def _removeLeadingZeros(self, s: str) -> str:
    index = next((i for i, c in enumerate(s) if c != '0'), -1)
    return ['0'] if index == -1 else s[index:]

Approach 2: re

• Time: $O(n)$
• Space: $O(n)$

Python

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