简单

问题描述

给你一个字符串 word ，该字符串由数字和小写英文字母组成。

请你用空格替换每个不是数字的字符。例如，"a123bc34d8ef34" 将会变成 " 123 34 8 34" 。注意，剩下的这些整数为（相邻彼此至少有一个空格隔开）："123"、"34"、"8" 和 "34" 。

返回对 word 完成替换后形成的 不同 整数的数目。

只有当两个整数的 不含前导零 的十进制表示不同， 才认为这两个整数也不同。

示例 1：

输入：word = "a123bc34d8ef34"
输出：3
解释：不同的整数有 "123"、"34" 和 "8" 。注意，"34" 只计数一次。

示例 2：

输入：word = "leet1234code234"
输出：2

示例 3：

输入：word = "a1b01c001"
输出：1
解释："1"、"01" 和 "001" 视为同一个整数的十进制表示，因为在比较十进制值时会忽略前导零的存在。

提示：

• 1 <= word.length <= 1000
• word 由数字和小写英文字母组成

双指针

对于字符串的数字部分，使用前指针 $i$ 指向数字第一个字符，后指针 $j$ 指向数字的最后一个字符，然后截取该整数部分，去掉前导零后放入 $HashSet$ 中，最终 $HashSet$ 的大小即为答案。

/**
 * @param {string} word
 * @return {number}
 */
var numDifferentIntegers = function (word) {
  const set = new Set()
  const n = word.length
  let i = 0
  while (i < n) {
    if (/[0-9]/.test(word[i])) {
      let j = i + 1
      while (/[0-9]/.test(word[j])) {
        j++
      }
      set.add(word.substring(i, j).replace(/^0+/, ''))
      i = j
    } else {
      i++
    }
  }
  return set.size
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$