Easy

题目描述

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

解题思路

这道题要求我们找出字符串中不同整数的数目。解题的关键是理解题目要求：

  1. 将非数字字符替换为空格
  2. 提取出所有整数
  3. 去除前导零后统计不同整数的数量

解法思路：

  1. 字符串处理法：遍历字符串，遇到数字字符时开始构建数字，遇到非数字字符时结束当前数字的构建。对于每个提取的数字，需要去除前导零。

  2. 正则表达式法：使用正则表达式直接提取所有数字序列，然后去除前导零。

  3. 状态机法：维护一个状态来判断当前是否在数字序列中。

推荐解法：字符串处理法 使用哈希集合存储去除前导零后的数字字符串，这样可以自动去重。遍历过程中，当遇到数字字符时累积构建当前数字，当遇到非数字字符或到达字符串末尾时，将当前数字（去除前导零后）加入集合。

去除前导零的方法：找到第一个非零字符的位置，如果全为零则返回"0"。

代码实现

class Solution {
public:
    int numDifferentIntegers(string word) {
        unordered_set<string> integers;
        string current = "";
        
        for (int i = 0; i < word.length(); i++) {
            if (isdigit(word[i])) {
                current += word[i];
            } else {
                if (!current.empty()) {
                    // 去除前导零
                    int start = 0;
                    while (start < current.length() && current[start] == '0') {
                        start++;
                    }
                    if (start == current.length()) {
                        integers.insert("0");
                    } else {
                        integers.insert(current.substr(start));
                    }
                    current = "";
                }
            }
        }
        
        // 处理最后一个数字
        if (!current.empty()) {
            int start = 0;
            while (start < current.length() && current[start] == '0') {
                start++;
            }
            if (start == current.length()) {
                integers.insert("0");
            } else {
                integers.insert(current.substr(start));
            }
        }
        
        return integers.size();
    }
};

class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        integers = set()
        current = ""
        
        for char in word:
            if char.isdigit():
                current += char
            else:
                if current:
                    # 去除前导零
                    normalized = current.lstrip('0') or '0'
                    integers.add(normalized)
                    current = ""
        
        # 处理最后一个数字
        if current:
            normalized = current.lstrip('0') or '0'
            integers.add(normalized)
        
        return len(integers)

public class Solution {
    public int NumDifferentIntegers(string word) {
        HashSet<string> integers = new HashSet<string>();
        string current = "";
        
        for (int i = 0; i < word.Length; i++) {
            if (char.IsDigit(word[i])) {
                current += word[i];
            } else {
                if (!string.IsNullOrEmpty(current)) {
                    // 去除前导零
                    string normalized = current.TrimStart('0');
                    if (string.IsNullOrEmpty(normalized)) {
                        normalized = "0";
                    }
                    integers.Add(normalized);
                    current = "";
                }
            }
        }
        
        // 处理最后一个数字
        if (!string.IsNullOrEmpty(current)) {
            string normalized = current.TrimStart('0');
            if (string.IsNullOrEmpty(normalized)) {
                normalized = "0";
            }
            integers.Add(normalized);
        }
        
        return integers.Count;
    }
}

var numDifferentIntegers = function(word) {
    const integers = new Set();
    let current = "";
    
    for (let i = 0; i < word.length; i++) {
        if (word[i] >= '0' && word[i] <= '9') {
            current += word[i];
        } else {
            if (current !== "") {
                // 去除前导零
                let normalized = current.replace(/^0+/, '') || '0';
                integers.add(normalized);
                current = "";
            }
        }
    }
    
    // 处理最后一个数字
    if (current !== "") {
        let normalized = current.replace(/^0+/, '') || '0';
        integers.add(normalized);
    }
    
    return integers.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)，其中 n 是字符串的长度，需要遍历整个字符串一次
空间复杂度O(k)，其中 k 是不同整数的数量，用于存储哈希集合

相关题目