江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第423题：从英文中重建数字

给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。

📖 文章摘要

本文详细解析LeetCode第423题“从英文中重建数字”，这是一道字符串处理和计数问题。文章提供了基于字符统计和规律匹配的解题思路，包含C#、Python、C++三种语言实现，配有详细的分析和性能对比。适合想要提升字符串处理能力的程序员。

核心知识点： 字符统计、贪心算法、字符串处理
难度等级： 中等
推荐人群： 具有基础算法知识的程序员

题目描述

给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。

示例

示例 1：

输入：s = "owoztneoer"
输出："012"

示例 2：

输入：s = "fviefuro"
输出："45"

提示

  • 1 <= s.length <= 105
  • s[i] 为 [“e”,“g”,“f”,“i”,“h”,“o”,“n”,“s”,“r”,“u”,“t”,“w”,“v”,“x”,“z”] 中的一个
  • s 保证是一个符合题目要求的字符串

解题思路

本题的关键是找到每个数字的英文单词中的特殊字符，通过这些特殊字符来确定数字的出现次数。我们可以通过以下步骤解决：

  1. 观察每个数字的英文单词：

    • zero: z唯一
    • two: w唯一
    • four: u唯一
    • six: x唯一
    • eight: g唯一
    • one: o（去掉zero、two、four的o后）
    • three: h（去掉eight的h后）
    • five: f（去掉four的f后）
    • seven: s（去掉six的s后）
    • nine: i（去掉five、six、eight的i后）

  2. 按照上述顺序统计字符出现次数，逐个确定每个数字的出现次数。

图解思路

字符统计分析表

数字 特征字符 单词 说明
0 z zero z只在zero中出现
2 w two w只在two中出现
4 u four u只在four中出现
6 x six x只在six中出现
8 g eight g只在eight中出现
3 h three 去掉eight后的h
5 f five 去掉four后的f
7 s seven 去掉six后的s
1 o one 去掉zero/two/four后的o
9 i nine 最后剩余的i

处理顺序表

步骤 处理数字 依据字符 后续处理
1 0,2,4,6,8 z,w,u,x,g 直接统计特征字符
2 3,5,7 h,f,s 减去之前数字的影响
3 1 o 减去0,2,4的影响
4 9 i 减去5,6,8的影响

代码实现

C# 实现

public class Solution {
    public string OriginalDigits(string s) {
        // 统计每个字符出现的次数
        int[] count = new int[26];
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        // 统计每个数字出现的次数
        int[] nums = new int[10];
        
        // 根据唯一字符确定数字
        nums[0] = count['z' - 'a'];  // zero
        nums[2] = count['w' - 'a'];  // two
        nums[4] = count['u' - 'a'];  // four
        nums[6] = count['x' - 'a'];  // six
        nums[8] = count['g' - 'a'];  // eight
        
        // 处理重叠字符
        nums[3] = count['h' - 'a'] - nums[8];  // three - eight
        nums[5] = count['f' - 'a'] - nums[4];  // five - four
        nums[7] = count['s' - 'a'] - nums[6];  // seven - six
        nums[1] = count['o' - 'a'] - nums[0] - nums[2] - nums[4];  // one - zero - two - four
        nums[9] = count['i' - 'a'] - nums[5] - nums[6] - nums[8];  // nine - five - six - eight
        
        // 构建结果字符串
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < 10; i++) {
            result.Append(new string((char)('0' + i), nums[i]));
        }
        
        return result.ToString();
    }
}

Python 实现

class Solution:
    def originalDigits(self, s: str) -> str:
        # 统计字符出现次数
        count = Counter(s)
        
        # 统计每个数字出现的次数
        nums = [0] * 10
        
        # 根据唯一字符确定数字
        nums[0] = count['z']  # zero
        nums[2] = count['w']  # two
        nums[4] = count['u']  # four
        nums[6] = count['x']  # six
        nums[8] = count['g']  # eight
        
        # 处理重叠字符
        nums[3] = count['h'] - nums[8]  # three - eight
        nums[5] = count['f'] - nums[4]  # five - four
        nums[7] = count['s'] - nums[6]  # seven - six
        nums[1] = count['o'] - nums[0] - nums[2] - nums[4]  # one - zero - two - four
        nums[9] = count['i'] - nums[5] - nums[6] - nums[8]  # nine - five - six - eight
        
        # 构建结果字符串
        return ''.join(str(i) * nums[i] for i in range(10))

C++ 实现

class Solution {
public:
    string originalDigits(string s) {
        // 统计字符出现次数
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        
        // 统计每个数字出现的次数
        vector<int> nums(10, 0);
        
        // 根据唯一字符确定数字
        nums[0] = count['z' - 'a'];  // zero
        nums[2] = count['w' - 'a'];  // two
        nums[4] = count['u' - 'a'];  // four
        nums[6] = count['x' - 'a'];  // six
        nums[8] = count['g' - 'a'];  // eight
        
        // 处理重叠字符
        nums[3] = count['h' - 'a'] - nums[8];  // three - eight
        nums[5] = count['f' - 'a'] - nums[4];  // five - four
        nums[7] = count['s' - 'a'] - nums[6];  // seven - six
        nums[1] = count['o' - 'a'] - nums[0] - nums[2] - nums[4];  // one - zero - two - four
        nums[9] = count['i' - 'a'] - nums[5] - nums[6] - nums[8];  // nine - five - six - eight
        
        // 构建结果字符串
        string result;
        for (int i = 0; i < 10; i++) {
            result += string(nums[i], '0' + i);
        }
        
        return result;
    }
};

执行结果

C# 实现

  • 执行用时：84 ms
  • 内存消耗：36.2 MB

Python 实现

  • 执行用时：44 ms
  • 内存消耗：15.1 MB

C++ 实现

  • 执行用时：4 ms
  • 内存消耗：6.8 MB

性能对比

语言 执行用时 内存消耗 特点
C# 84 ms 36.2 MB 代码结构清晰，但性能较差
Python 44 ms 15.1 MB 代码简洁，性能中等
C++ 4 ms 6.8 MB 性能最优，内存占用最小

代码亮点

  1. 🎯 利用字符唯一性巧妙解决重叠问题
  2. 💡 使用数组统计优化性能
  3. 🔍 按特定顺序处理避免干扰
  4. 🎨 代码结构清晰，注释完整

常见错误分析

  1. 🚫 忽略字符重叠情况
  2. 🚫 处理顺序错误导致统计错误
  3. 🚫 未考虑数字出现多次的情况
  4. 🚫 字符统计数组越界

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
字符统计法 O(n) O(1) 实现简单，性能好 依赖字符唯一性
暴力匹配法 O(n²) O(n) 思路直观 性能差

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第423题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！