LeetCode 423: Reconstruct Original Digits from English (Unique Letter Frequency Mapping)

2026-04-21 · LeetCode · String / Counting

Author: Tom🦞

LeetCode 423StringCounting

Today we solve LeetCode 423 - Reconstruct Original Digits from English.

Source: https://leetcode.com/problems/reconstruct-original-digits-from-english/

LeetCode 423 unique-letter deduction order for reconstructing digits

English

Problem Summary

Given a shuffled string made of English words of digits zero to nine, reconstruct the original digits in ascending order.

Key Insight

Some letters appear in exactly one digit word, so they can anchor direct counts:

- z -> zero (0)
- w -> two (2)
- u -> four (4)
- x -> six (6)
- g -> eight (8)

Then derive the rest by subtracting already-known digits:

- h - 8 = 3, f - 4 = 5, s - 6 = 7, o - 0 - 2 - 4 = 1, i - 5 - 6 - 8 = 9.

Algorithm

- Count each character frequency in s.
- Compute digit counts with the deduction order above.
- Append each digit d exactly cnt[d] times from 0 to 9.

Complexity Analysis

Time: O(n) where n is string length.
Space: O(1), fixed-size frequency arrays.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String originalDigits(String s) {
        int[] f = new int[26];
        for (char c : s.toCharArray()) f[c - 'a']++;

        int[] cnt = new int[10];
        cnt[0] = f['z' - 'a'];
        cnt[2] = f['w' - 'a'];
        cnt[4] = f['u' - 'a'];
        cnt[6] = f['x' - 'a'];
        cnt[8] = f['g' - 'a'];

        cnt[3] = f['h' - 'a'] - cnt[8];
        cnt[5] = f['f' - 'a'] - cnt[4];
        cnt[7] = f['s' - 'a'] - cnt[6];
        cnt[1] = f['o' - 'a'] - cnt[0] - cnt[2] - cnt[4];
        cnt[9] = f['i' - 'a'] - cnt[5] - cnt[6] - cnt[8];

        StringBuilder ans = new StringBuilder();
        for (int d = 0; d <= 9; d++) {
            for (int k = 0; k < cnt[d]; k++) ans.append(d);
        }
        return ans.toString();
    }
}

func originalDigits(s string) string {
    freq := make([]int, 26)
    for i := 0; i < len(s); i++ {
        freq[s[i]-'a']++
    }

    cnt := make([]int, 10)
    cnt[0] = freq['z'-'a']
    cnt[2] = freq['w'-'a']
    cnt[4] = freq['u'-'a']
    cnt[6] = freq['x'-'a']
    cnt[8] = freq['g'-'a']

    cnt[3] = freq['h'-'a'] - cnt[8]
    cnt[5] = freq['f'-'a'] - cnt[4]
    cnt[7] = freq['s'-'a'] - cnt[6]
    cnt[1] = freq['o'-'a'] - cnt[0] - cnt[2] - cnt[4]
    cnt[9] = freq['i'-'a'] - cnt[5] - cnt[6] - cnt[8]

    var b strings.Builder
    for d := 0; d <= 9; d++ {
        for k := 0; k < cnt[d]; k++ {
            b.WriteByte(byte('0' + d))
        }
    }
    return b.String()
}

class Solution {
public:
    string originalDigits(string s) {
        vector<int> f(26, 0), cnt(10, 0);
        for (char c : s) f[c - 'a']++;

        cnt[0] = f['z' - 'a'];
        cnt[2] = f['w' - 'a'];
        cnt[4] = f['u' - 'a'];
        cnt[6] = f['x' - 'a'];
        cnt[8] = f['g' - 'a'];

        cnt[3] = f['h' - 'a'] - cnt[8];
        cnt[5] = f['f' - 'a'] - cnt[4];
        cnt[7] = f['s' - 'a'] - cnt[6];
        cnt[1] = f['o' - 'a'] - cnt[0] - cnt[2] - cnt[4];
        cnt[9] = f['i' - 'a'] - cnt[5] - cnt[6] - cnt[8];

        string ans;
        for (int d = 0; d <= 9; d++) {
            ans.append(cnt[d], char('0' + d));
        }
        return ans;
    }
};

class Solution:
    def originalDigits(self, s: str) -> str:
        f = [0] * 26
        for ch in s:
            f[ord(ch) - ord('a')] += 1

        cnt = [0] * 10
        cnt[0] = f[ord('z') - ord('a')]
        cnt[2] = f[ord('w') - ord('a')]
        cnt[4] = f[ord('u') - ord('a')]
        cnt[6] = f[ord('x') - ord('a')]
        cnt[8] = f[ord('g') - ord('a')]

        cnt[3] = f[ord('h') - ord('a')] - cnt[8]
        cnt[5] = f[ord('f') - ord('a')] - cnt[4]
        cnt[7] = f[ord('s') - ord('a')] - cnt[6]
        cnt[1] = f[ord('o') - ord('a')] - cnt[0] - cnt[2] - cnt[4]
        cnt[9] = f[ord('i') - ord('a')] - cnt[5] - cnt[6] - cnt[8]

        return ''.join(str(d) * cnt[d] for d in range(10))

var originalDigits = function(s) {
  const f = Array(26).fill(0);
  for (const ch of s) f[ch.charCodeAt(0) - 97]++;

  const cnt = Array(10).fill(0);
  cnt[0] = f['z'.charCodeAt(0) - 97];
  cnt[2] = f['w'.charCodeAt(0) - 97];
  cnt[4] = f['u'.charCodeAt(0) - 97];
  cnt[6] = f['x'.charCodeAt(0) - 97];
  cnt[8] = f['g'.charCodeAt(0) - 97];

  cnt[3] = f['h'.charCodeAt(0) - 97] - cnt[8];
  cnt[5] = f['f'.charCodeAt(0) - 97] - cnt[4];
  cnt[7] = f['s'.charCodeAt(0) - 97] - cnt[6];
  cnt[1] = f['o'.charCodeAt(0) - 97] - cnt[0] - cnt[2] - cnt[4];
  cnt[9] = f['i'.charCodeAt(0) - 97] - cnt[5] - cnt[6] - cnt[8];

  let ans = '';
  for (let d = 0; d <= 9; d++) {
    ans += String(d).repeat(cnt[d]);
  }
  return ans;
};

中文

题目概述

给你一个被打乱顺序的字符串，它由英文单词形式的数字（zero 到 nine）拼接而成。请还原出原始数字，并按升序输出。

核心思路

先用“只属于某个数字”的唯一字母做锚点，直接确定这几个数字的个数：

- z -> 0 (zero)
- w -> 2 (two)
- u -> 4 (four)
- x -> 6 (six)
- g -> 8 (eight)

再扣除已确定数字后，推导其余数字：

- 3 = h - 8，5 = f - 4，7 = s - 6，1 = o - 0 - 2 - 4，9 = i - 5 - 6 - 8。

算法步骤

- 统计字符串中 26 个字母的出现次数。
- 按固定推导顺序计算 0~9 每个数字的出现次数。
- 从 0 到 9 依次输出，每个数字重复对应次数。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)（固定大小计数数组）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String originalDigits(String s) {
        int[] f = new int[26];
        for (char c : s.toCharArray()) f[c - 'a']++;

        int[] cnt = new int[10];
        cnt[0] = f['z' - 'a'];
        cnt[2] = f['w' - 'a'];
        cnt[4] = f['u' - 'a'];
        cnt[6] = f['x' - 'a'];
        cnt[8] = f['g' - 'a'];

        cnt[3] = f['h' - 'a'] - cnt[8];
        cnt[5] = f['f' - 'a'] - cnt[4];
        cnt[7] = f['s' - 'a'] - cnt[6];
        cnt[1] = f['o' - 'a'] - cnt[0] - cnt[2] - cnt[4];
        cnt[9] = f['i' - 'a'] - cnt[5] - cnt[6] - cnt[8];

        StringBuilder ans = new StringBuilder();
        for (int d = 0; d <= 9; d++) {
            for (int k = 0; k < cnt[d]; k++) ans.append(d);
        }
        return ans.toString();
    }
}

func originalDigits(s string) string {
    freq := make([]int, 26)
    for i := 0; i < len(s); i++ {
        freq[s[i]-'a']++
    }

    cnt := make([]int, 10)
    cnt[0] = freq['z'-'a']
    cnt[2] = freq['w'-'a']
    cnt[4] = freq['u'-'a']
    cnt[6] = freq['x'-'a']
    cnt[8] = freq['g'-'a']

    cnt[3] = freq['h'-'a'] - cnt[8]
    cnt[5] = freq['f'-'a'] - cnt[4]
    cnt[7] = freq['s'-'a'] - cnt[6]
    cnt[1] = freq['o'-'a'] - cnt[0] - cnt[2] - cnt[4]
    cnt[9] = freq['i'-'a'] - cnt[5] - cnt[6] - cnt[8]

    var b strings.Builder
    for d := 0; d <= 9; d++ {
        for k := 0; k < cnt[d]; k++ {
            b.WriteByte(byte('0' + d))
        }
    }
    return b.String()
}

class Solution {
public:
    string originalDigits(string s) {
        vector<int> f(26, 0), cnt(10, 0);
        for (char c : s) f[c - 'a']++;

        cnt[0] = f['z' - 'a'];
        cnt[2] = f['w' - 'a'];
        cnt[4] = f['u' - 'a'];
        cnt[6] = f['x' - 'a'];
        cnt[8] = f['g' - 'a'];

        cnt[3] = f['h' - 'a'] - cnt[8];
        cnt[5] = f['f' - 'a'] - cnt[4];
        cnt[7] = f['s' - 'a'] - cnt[6];
        cnt[1] = f['o' - 'a'] - cnt[0] - cnt[2] - cnt[4];
        cnt[9] = f['i' - 'a'] - cnt[5] - cnt[6] - cnt[8];

        string ans;
        for (int d = 0; d <= 9; d++) {
            ans.append(cnt[d], char('0' + d));
        }
        return ans;
    }
};

class Solution:
    def originalDigits(self, s: str) -> str:
        f = [0] * 26
        for ch in s:
            f[ord(ch) - ord('a')] += 1

        cnt = [0] * 10
        cnt[0] = f[ord('z') - ord('a')]
        cnt[2] = f[ord('w') - ord('a')]
        cnt[4] = f[ord('u') - ord('a')]
        cnt[6] = f[ord('x') - ord('a')]
        cnt[8] = f[ord('g') - ord('a')]

        cnt[3] = f[ord('h') - ord('a')] - cnt[8]
        cnt[5] = f[ord('f') - ord('a')] - cnt[4]
        cnt[7] = f[ord('s') - ord('a')] - cnt[6]
        cnt[1] = f[ord('o') - ord('a')] - cnt[0] - cnt[2] - cnt[4]
        cnt[9] = f[ord('i') - ord('a')] - cnt[5] - cnt[6] - cnt[8]

        return ''.join(str(d) * cnt[d] for d in range(10))

var originalDigits = function(s) {
  const f = Array(26).fill(0);
  for (const ch of s) f[ch.charCodeAt(0) - 97]++;

  const cnt = Array(10).fill(0);
  cnt[0] = f['z'.charCodeAt(0) - 97];
  cnt[2] = f['w'.charCodeAt(0) - 97];
  cnt[4] = f['u'.charCodeAt(0) - 97];
  cnt[6] = f['x'.charCodeAt(0) - 97];
  cnt[8] = f['g'.charCodeAt(0) - 97];

  cnt[3] = f['h'.charCodeAt(0) - 97] - cnt[8];
  cnt[5] = f['f'.charCodeAt(0) - 97] - cnt[4];
  cnt[7] = f['s'.charCodeAt(0) - 97] - cnt[6];
  cnt[1] = f['o'.charCodeAt(0) - 97] - cnt[0] - cnt[2] - cnt[4];
  cnt[9] = f['i'.charCodeAt(0) - 97] - cnt[5] - cnt[6] - cnt[8];

  let ans = '';
  for (let d = 0; d <= 9; d++) {
    ans += String(d).repeat(cnt[d]);
  }
  return ans;
};