423. 从英文中重建数字

🟠   🔖  哈希表 数学 字符串  🔗 力扣 LeetCode

题目

Given a string s containing an out-of-order English representation of digits 0-9, return the digits inascending order.

Example 1:

Input: s = "owoztneoer"

Output: "012"

Example 2:

Input: s = "fviefuro"

Output: "45"

Constraints:

• 1 <= s.length <= 10^5
• s[i] is one of the characters ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"].
• s is guaranteed to be valid.

题目大意

给你一个字符串 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 保证是一个符合题目要求的字符串

解题思路

1. 统计字符频次

   • 使用哈希表 count 统计 s 中每个字符的出现次数。

2. 确定唯一标识数字的字符

   • 观察单词拼写，某些字母只会出现在特定数字单词中：
     • "z" 只出现在 "zero" → 确定 0 的数量
     • "w" 只出现在 "two" → 确定 2 的数量
     • "x" 只出现在 "six" → 确定 6 的数量
     • "g" 只出现在 "eight" → 确定 8 的数量

3. 处理剩余的数字

   • 由于 "three" 中包含 "t"，但 2 和 8 也含 "t"，所以 3 需要等 2 和 8 处理完后计算。
   • 依次推导 "four", "five", "seven", "nine", "one"，确保它们不受前面数字的影响。

4. 按数字顺序排序

   • 将 res 数组按升序排列并返回结果。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。
  • 字符统计：遍历 s，构建哈希表，O(n)。
  • 提取数字：最多遍历 s 长度的字符，O(n)。
  • 排序：提取的数字最多 O(10log10) = O(1)。
  • 最终合并结果：O(n)。
• 空间复杂度：O(m)，其中 m 是结果字符串 res 的长度。

代码

/**
 * @param {string} s
 * @return {string}
 */
var originalDigits = function (s) {
	let count = {};
	for (let char of s) {
		if (!(char in count)) {
			count[char] = 1;
		} else {
			count[char]++;
		}
	}
	let res = [];
	while (count['z']) {
		res.push(0);
		count['z']--;
		count['e']--;
		count['r']--;
		count['o']--;
	}
	while (count['w']) {
		res.push(2);
		count['t']--;
		count['w']--;
		count['o']--;
	}
	while (count['x']) {
		res.push(6);
		count['s']--;
		count['i']--;
		count['x']--;
	}
	while (count['g']) {
		res.push(8);
		count['e']--;
		count['i']--;
		count['g']--;
		count['h']--;
		count['t']--;
	}
	while (count['t']) {
		res.push(3);
		count['t']--;
		count['h']--;
		count['r']--;
		count['e'] -= 2;
	}
	while (count['r']) {
		res.push(4);
		count['f']--;
		count['o']--;
		count['u']--;
		count['r']--;
	}
	while (count['f']) {
		res.push(5);
		count['f']--;
		count['i']--;
		count['v']--;
		count['e']--;
	}
	while (count['s']) {
		res.push(7);
		count['s']--;
		count['e'] -= 2;
		count['v']--;
		count['n']--;
	}
	while (count['i']) {
		res.push(9);
		count['n'] -= 2;
		count['i']--;
		count['e']--;
	}
	while (count['o']) {
		res.push(1);
		count['o']--;
		count['n']--;
		count['e']--;
	}
	return res.sort().join('');
};