[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

代码如下所示:

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. 😉😃💗