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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

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\)。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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. 😉😃💗