0423. Reconstruct Original Digits from English =============================================== 题目信息 -------- :题号: 0423 :难度: Medium :主题: 英文数字单词、字符频次、原始数字、多重集合恢复 :原题: `LeetCode 0423 `_ :重点: 输入字母来自若干 ``zero`` 至 ``nine`` 的乱序拼接、数字可以重复、结果按数字升序输出 题目重述 -------- 给定只包含小写英文字母的字符串 ``s``。它由若干个英文数字单词 ``"zero"``、``"one"``、…、``"nine"`` 的全部字母混合打乱后得到。恢复原来包含的所有数字,并将这些数字按从小到大的顺序连接成字符串返回。 ``s.length`` 位于 ``[1, 10^5]``。同一个数字可以出现多次,输入保证能够由完整的英文数字单词组成,不会有多余或缺失字母。返回结果中的每个字符代表一个恢复出的数字,不需要恢复原单词顺序。 自建示例 -------- 恢复两个不同数字: .. code-block:: text 输入:s = "fviefuro" 输出:"45" 解释:这些字母可以拆成 four 和 five;结果必须按数字升序写成 45,与字母原来的排列顺序无关。 同一数字重复出现: .. code-block:: text 输入:s = "xisxis" 输出:"66" 解释:字符串由两个 six 的字母组成,因此数字 6 需要在结果中保留两次。 利用只在一个数字单词中出现的字母 ---------------------------------- 字母 ``z,w,u,x,g`` 分别只出现在 ``zero,two,four,six,eight`` 中,所以可以先确定数字 0、2、4、6、8 的数量。确定这些数字后,再利用 ``o,h,f,s,i`` 的剩余数量依次求出 1、3、5、7、9;每求出一个数字就从总字符频次中扣除对应单词,剩余频次因此仍有明确含义。 最后按数字从 0 到 9 输出数量次数字字符,字母原来的打乱顺序不会影响结果。 C++ 实现 -------- .. code-block:: cpp class Solution { public: std::string originalDigits(std::string s) { std::array count{}; for (char c : s) ++count[c - 'a']; std::array number{}; number[0] = count['z' - 'a']; number[2] = count['w' - 'a']; number[4] = count['u' - 'a']; number[6] = count['x' - 'a']; number[8] = count['g' - 'a']; number[1] = count['o' - 'a'] - number[0] - number[2] - number[4]; number[3] = count['h' - 'a'] - number[8]; number[5] = count['f' - 'a'] - number[4]; number[7] = count['s' - 'a'] - number[6]; number[9] = count['i' - 'a'] - number[5] - number[6] - number[8]; std::string result; for (int digit = 0; digit <= 9; ++digit) { result.append(number[digit], static_cast('0' + digit)); } return result; } }; 代码分析 -------- 唯一字母先锁定偶数数字,后续扣除已确认单词后再恢复其余数字;输入保证可由完整单词组成,因此计算出的数量非负且恰好消耗全部字符。统计和输出均为线性,时间复杂度为 ``O(|s|)``,额外空间为固定的 ``O(1)``(不计返回字符串)。