423. 从英文中重建数字

Medium

题目描述

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

示例 1：

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

示例 2：

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

提示：

1 <= s.length <= 10^5
s[i] 是 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 中的一个字符
s 保证是一个有效的字符串

解题思路

这道题的关键是找到每个数字英文单词的特征字符，通过这些字符来唯一识别数字。

我们需要分析 0-9 的英文单词：

zero, one, two, three, four, five, six, seven, eight, nine

核心思路：

有些数字包含独特字符，可以直接确定：
- ‘z’ 只出现在 zero 中 → 确定数字 0 的个数
- ‘w’ 只出现在 two 中 → 确定数字 2 的个数
- ‘u’ 只出现在 four 中 → 确定数字 4 的个数
- ‘x’ 只出现在 six 中 → 确定数字 6 的个数
- ‘g’ 只出现在 eight 中 → 确定数字 8 的个数
确定了这些数字后，可以通过其他字符推导：
- ‘f’ 出现在 four 和 five 中，减去 four 的个数得到 five
- ’s’ 出现在 six 和 seven 中，减去 six 的个数得到 seven
- ‘h’ 出现在 three 和 eight 中，减去 eight 的个数得到 three
- ‘i’ 出现在 five, six, eight, nine 中，减去前面确定的得到 nine
- ‘o’ 出现在 zero, one, two, four 中，减去前面确定的得到 one
最后按升序构造结果字符串。

代码实现

class Solution {
public:
    string originalDigits(string s) {
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }
        
        vector<int> digits(10, 0);
        
        // 先确定有独特字符的数字
        digits[0] = count['z' - 'a'];  // zero
        digits[2] = count['w' - 'a'];  // two
        digits[4] = count['u' - 'a'];  // four
        digits[6] = count['x' - 'a'];  // six
        digits[8] = count['g' - 'a'];  // eight
        
        // 再确定其他数字
        digits[5] = count['f' - 'a'] - digits[4];  // five (f appears in four and five)
        digits[7] = count['s' - 'a'] - digits[6];  // seven (s appears in six and seven)
        digits[3] = count['h' - 'a'] - digits[8];  // three (h appears in three and eight)
        digits[9] = count['i' - 'a'] - digits[5] - digits[6] - digits[8];  // nine
        digits[1] = count['o' - 'a'] - digits[0] - digits[2] - digits[4];  // one
        
        string result = "";
        for (int i = 0; i < 10; i++) {
            result += string(digits[i], '0' + i);
        }
        
        return result;
    }
};

class Solution:
    def originalDigits(self, s: str) -> str:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        
        digits = [0] * 10
        
        # 先确定有独特字符的数字
        digits[0] = count[ord('z') - ord('a')]  # zero
        digits[2] = count[ord('w') - ord('a')]  # two
        digits[4] = count[ord('u') - ord('a')]  # four
        digits[6] = count[ord('x') - ord('a')]  # six
        digits[8] = count[ord('g') - ord('a')]  # eight
        
        # 再确定其他数字
        digits[5] = count[ord('f') - ord('a')] - digits[4]  # five
        digits[7] = count[ord('s') - ord('a')] - digits[6]  # seven
        digits[3] = count[ord('h') - ord('a')] - digits[8]  # three
        digits[9] = count[ord('i') - ord('a')] - digits[5] - digits[6] - digits[8]  # nine
        digits[1] = count[ord('o') - ord('a')] - digits[0] - digits[2] - digits[4]  # one
        
        result = ""
        for i in range(10):
            result += str(i) * digits[i]
        
        return result

public class Solution {
    public string OriginalDigits(string s) {
        int[] count = new int[26];
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        int[] digits = new int[10];
        
        // 先确定有独特字符的数字
        digits[0] = count['z' - 'a'];  // zero
        digits[2] = count['w' - 'a'];  // two
        digits[4] = count['u' - 'a'];  // four
        digits[6] = count['x' - 'a'];  // six
        digits[8] = count['g' - 'a'];  // eight
        
        // 再确定其他数字
        digits[5] = count['f' - 'a'] - digits[4];  // five
        digits[7] = count['s' - 'a'] - digits[6];  // seven
        digits[3] = count['h' - 'a'] - digits[8];  // three
        digits[9] = count['i' - 'a'] - digits[5] - digits[6] - digits[8];  // nine
        digits[1] = count['o' - 'a'] - digits[0] - digits[2] - digits[4];  // one
        
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < digits[i]; j++) {
                result.Append(i);
            }
        }
        
        return result.ToString();
    }
}

var originalDigits = function(s) {
    const count = new Array(26).fill(0);
    for (const c of s) {
        count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    const digits = new Array(10).fill(0);
    
    // 先确定有独特字符的数字
    digits[0] = count['z'.charCodeAt(0) - 'a'.charCodeAt(0)];  // zero
    digits[2] = count['w'.charCodeAt(0) - 'a'.charCodeAt(0)];  // two
    digits[4] = count['u'.charCodeAt(0) - 'a'.charCodeAt(0)];  // four
    digits[6] = count['x'.charCodeAt(0) - 'a'.charCodeAt(0)];  // six
    digits[8] = count['g'.charCodeAt(0) - 'a'.charCodeAt(0)];  // eight
    
    // 再确定其他数字
    digits[5] = count['f'.charCodeAt(0) - 'a'.charCodeAt(0)] - digits[4];  // five
    digits[7] = count['s'.charCodeAt(0) - 'a'.charCodeAt(0)] - digits[6];  // seven
    digits[3] = count['h'.charCodeAt(0) - 'a'.charCodeAt(0)] - digits[8];  // three
    digits[9] = count['i'.charCodeAt(0) - 'a'.charCodeAt(0)] - digits[5] - digits[6] - digits[8];  // nine
    digits[1] = count['o'.charCodeAt(0) - 'a'.charCodeAt(0)] - digits[0] - digits[2] - digits[4];  // one
    
    let result = "";
    for (let i = 0; i < 10; i++) {
        result += i.toString().repeat(digits[i]);
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值
时间复杂度	O(n)
空间复杂度	O(1)

其中 n 是字符串 s 的长度。我们只需要遍历一次字符串来统计字符频率，然后通过常数次操作确定各个数字的个数。空间复杂度是常数级别，因为我们只使用了固定大小的数组。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析