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

By Long Luo

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

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

思路与算法:

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

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

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

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

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

代码如下所示:

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)O(|s|),其中 s|s| 是字符串 ss 的长度。

  • 空间复杂度:O(Σ)O(|\Sigma|),其中 Σ\Sigma 表示字符集,Σ|\Sigma| 表示字符集的大小,在本题中 Σ\Sigma 为所有在 090 \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. 😉😃💗