题目描述

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

示例 1：

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

示例 2：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reconstruct-original-digits-from-english
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

• 今天的算法每日一题是字符串处理题目，题意要求从乱序的英文字符串中重新构建数字。并按照数字升序返回。

• 我们首先需要枚举0 ～ 9 的英文，["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"], 然后归纳总结发现，z, w, u, x, g都只在一个数字中，即0,2,4,6,8 中出现。同时，字符 h 只在 3,8 中出现。由于我们已经知道了 8 出现的次数，因此可以计算出 3 出现的次数。字符 f 只在 4,5 中出现。由于我们已经知道了 4 出现的次数，因此可以计算出 5 出现的次数。字符 s 只在 6, 7 中出现。由于我们已经知道了 6 出现的次数，因此可以计算出 7 出现的次数。o 只在 0, 1, 2, 4 中出现，由于我们已经知道了 0, 2, 4 出现的次数，因此可以计算出 1 出现的次数。i 在 5, 6, 8, 9 中出现，由于我们已经知道了 5, 6, 8 出现的次数，因此可以计算出 9 出现的次数。

• 根据上述观察分析的结论，我们在使用 hashmap 统计 s 的字符数据。就可以得到答案。具体实现如下：

通过代码

class Solution {
    public String originalDigits(String s) {
        Map c = new HashMap();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            c.put(ch, c.getOrDefault(ch, 0) + 1);
        }

        int[] cnt = new int[10];
        cnt[0] = c.getOrDefault('z', 0);
        cnt[2] = c.getOrDefault('w', 0);
        cnt[4] = c.getOrDefault('u', 0);
        cnt[6] = c.getOrDefault('x', 0);
        cnt[8] = c.getOrDefault('g', 0);

        cnt[3] = c.getOrDefault('h', 0) - cnt[8];
        cnt[5] = c.getOrDefault('f', 0) - cnt[4];
        cnt[7] = c.getOrDefault('s', 0) - cnt[6];

        cnt[1] = c.getOrDefault('o', 0) - cnt[0] - cnt[2] - cnt[4];

        cnt[9] = c.getOrDefault('i', 0) - cnt[5] - cnt[6] - cnt[8];

        StringBuffer ans = new StringBuffer();
        for (int i = 0; i < 10; ++i) {
            for (int j = 0; j < cnt[i]; ++j) {
                ans.append((char) (i + '0'));
            }
        }
        return ans.toString();
    }
}

总结

• 上述代码的时间复杂度是O(n),空间复杂度是O(n)

• 坚持算法每日一题，加油！