How do I handle leading zeros in this problem?

Convert each numeric substring to an integer or strip leading zeros before inserting into a set to ensure correct uniqueness counting.

Can I solve this without a hash table?

Yes, but it requires more complex comparison logic to check uniqueness manually, which is less efficient and prone to errors.

What is the main pattern used in Number of Different Integers in a String?

The key pattern is Hash Table plus String, focusing on parsing and deduplicating numeric substrings extracted from letters and digits.

Does splitting by non-digit characters always work?

Yes, as long as all non-digit characters are replaced with a consistent separator, splitting ensures each integer is isolated for counting.

What should I watch out for with large input strings?

Ensure that parsing and hash table insertion are linear in time and avoid unnecessary string copies to handle up to 1000 characters efficiently.

#1805

Easy

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

字符串中不同整数的数目

给你一个字符串 word ，该字符串由数字和小写英文字母组成。请你用空格替换每个不是数字的字符。例如， "a123bc34d8ef34" 将会变成 " 123 34 8 34" 。注意，剩下的这些整数为（相邻彼此至少有一个空格隔开）： "123" 、 "34" 、 "8" 和 "34" 。返回对…

哈希表字符串

题目描述

给你一个字符串 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 由数字和小写英文字母组成

lightbulb

解题思路

方法一：双指针 + 模拟

遍历字符串 word，找到每个整数的起始位置和结束位置，截取出这一个子串，将其存入哈希表 $s$ 中。

遍历结束，返回哈希表 $s$ 的大小即可。

注意，每个子串所表示的整数可能很大，我们不能直接将其转为整数。因此，我们可以去掉每个子串的前导零之后，再存入哈希表。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 word 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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)

speed

复杂度分析

指标	值
时间	complexity is O(n) where n is the string length, as each character is processed once and inserting into a hash table is O(1) on average. Space complexity is O(k) for storing k unique integers in the hash table.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for candidates using string parsing combined with a hash table.
question_mark
Watch for handling of leading zeros as a subtle failure mode.
question_mark
Expect a clean separation of letters and digits before counting unique numbers.

warning

常见陷阱

外企场景

error
Counting numeric substrings without removing leading zeros, causing duplicates to appear.
error
Using nested loops for comparison instead of a hash table, increasing complexity.
error
Failing to replace all non-digit characters, which can merge integers incorrectly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count distinct integers ignoring case-insensitive letters in a string.
arrow_right_alt
Return both the unique integer count and the list of integers in sorted order.
arrow_right_alt
Handle strings where integers are separated by multiple non-digit characters or punctuation.

help

常见问题

外企场景

继续练习

#1807 替换字符串中的括号内容 #1796 字符串中第二大的数字 #1790 仅执行一次字符串交换能否使两个字符串相等