[LeetCode][423. 从英文中重建数字] 找规律，依次确定数字的次数，逐步消元法

By Long Luo

Leetcode 423. 从英文中重建数字 题解。

方法一：按照独占性依次确定每一个数字的次数

思路与算法：

最开始，看到这道题我是懵逼的，字符串怎么变成一串数字，按照什么规律，认真读了几遍，参考示例才明白啥意思。

每个数字都对应一个英文单词，$zero, one, two, three, four, five, six, seven, eight, nine$，统计每个英文字母在这些单词中出现的情况，发现有些字母只出现在某一个单词里，而有些字母则会出现在很多单词里。

比如 $z$ 就只出现在 $zero$ 里，$g$ 只出现在 $eight$ 里。 而 $i$ 则同时出现在了 $five, six, eight, nine$ 中，那么我们需要先求出乱序的字符串中每个数字包含了多少个，然后按照升序进行排列。

那么我们先对乱序字符串遍历计数，按照独占性，先把特定数字中的单词数量找出来，比如出现多少个 $z$，就一定有多少个 $0$。然后再把 $0$ 中出现的字母去掉，逐步消元。

那么我们可以先统计每个字母的个数，然后减去对应数字的单词字母数，直至都为 $0$。

代码如下所示：

public String originalDigits(String s) {
    Map<Character, Integer> map = new HashMap<Character, Integer>();
    for (int i = 0; i < s.length(); ++i) {
        map.put(s.charAt(i), map.getOrDefault(ch, 0) + 1);
    }

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

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

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

    cnt[9] = map.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(|s|)$，其中 $|s|$ 是字符串 $s$ 的长度。

• 空间复杂度：$O(|\Sigma|)$，其中 $\Sigma$ 表示字符集，$|\Sigma|$ 表示字符集的大小，在本题中 $\Sigma$ 为所有在 $0 \sim 9$ 中出现的英文字母。

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗