1805. 字符串中不同整数的数目

🟢   🔖  哈希表 字符串  🔗 力扣 LeetCode

题目

You are given a string word that consists of digits and lowercase English letters.

You will replace every non-digit character with a space. For example, "a123bc34d8ef34" will become " 123 34 8 34". Notice that you are left with some integers that are separated by at least one space: "123", "34", "8", and "34".

Return _the number ofdifferent integers after performing the replacement operations on _word.

Two integers are considered different if their decimal representations without any leading zeros are different.

Example 1:

Input: word = "a 123 bc 34 d 8 ef 34 "

Output: 3

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

Example 2:

Input: word = "leet 1234 code 234 "

Output: 2

Example 3:

Input: word = "a 1 b 01 c 001 "

Output: 1

Explanation: The three integers "1", "01", and "001" all represent the same integer because

the leading zeros are ignored when comparing their decimal values.

Constraints:

• 1 <= word.length <= 1000
• word consists of digits and lowercase English letters.

题目大意

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

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

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

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

示例 1：

输入： word = "a123 bc34 d8 ef34 "

输出： 3

解释： 不同的整数有 "123"、"34" 和 "8" 。注意，"34" 只计数一次。

示例 2：

输入： word = "leet1234 code234 "

输出： 2

示例 3：

输入： word = "a1 b01 c001 "

输出： 1

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

提示：

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

解题思路

解题思路

该问题要求我们从给定的字符串 word 中提取不同的整数个数。字符串中包含字母和数字，数字可能由字母分隔。目标是找到所有不同的整数，并返回其个数。

步骤分析

1. 移除字母：/[a-z]/g：用于匹配字符串中的所有小写字母。通过 replace 将所有字母替换为空格，确保字母不干扰数字的提取。
2. 分割数字：使用空格将字符串分割，得到所有数字的子字符串。
3. 过滤空字符串：去除任何空字符串，确保仅保留有效的数字部分。
4. 去除前导零：将每个数字字符串转换成 BigInt，确保我们可以处理大数字并去除前导零。为了避免整数溢出问题，使用 BigInt 来存储和比较大数字。
5. 使用 Set：通过 Set 去重，确保每个整数只出现一次。
6. 返回结果：返回 Set 的大小，即不同整数的个数。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。正则替换，split 和 map 都需要遍历一遍字符串。
• 空间复杂度：O(n)，主要是存储处理后的数字。

代码

/**
 * @param {string} word
 * @return {number}
 */
var numDifferentIntegers = function (word) {
	// 替换所有字母为 ' '，然后分割成数字
	let set = new Set(
		word
			.replace(/[a-z]/g, ' ')
			.split(' ')
			.filter((i) => i !== '')
			.map(BigInt)
	);
	return set.size;
};

相关题目

题号	标题	题解	标签	难度	力扣
2419	按位与最大的最长子数组		位运算 脑筋急转弯 数组	🟠	🀄️ 🔗