[Leetcode 423] Reconstruct Original Digits from English

作者 Shilei Tian 日期 2017-01-03
[Leetcode 423] Reconstruct Original Digits from English

题目要求

Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.

Note:

  1. Input contains only lowercase English letters.
  2. Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as “abc” or “zerone” are not permitted.
  3. Input length is less than 50,000.

Example 1:

Input: “owoztneoer”

Output: “012”

Example 2:

Input: “fviefuro”

Output: “45”

解题思路

这道题目的要求很简单,就是从一堆乱序的英文字符串中重新构建出数字串来,很容易想到的一个方法是 Hash 方法,代码如下:

class Solution {
public:
string originalDigits(string s) {
unordered_map<char, int> map;
vector<string> nums = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
for (auto ch : s) {
map[ch]++;
}
string ret;
for (int i = 0; i < 10; ++i) {
bool sat = true;
int min = INT_MAX;
for (auto ch : nums[i]) {
if (map[ch] == 0) {
sat = false;
} else if (map[ch] < min) {
min = map[ch];
}
}
if (!sat) {
continue;
}
for (auto ch : nums[i]) {
map[ch] -= min;
}
ret += string(min, i + '0');
}
return ret;
}
};

但是很不幸,虽然题给条件说字符串长度不超过 50,000,上面这段代码的时间复杂度为 $O(n)$,依然会超时。那应该怎么做呢?

我们知道,0 对应的英文单词是 zero,在 0-9 对应的英文单词中,z 只在 0 中出现,那么就是说,最终输出串中 0 的个数等于 z 的个数。那按照这个思路,我们同理可得,2 的个数应该等于 w 的个数,4 的个数应该等于 u 的个数,6 的个数等于 x 的个数,8 的个数等于 g 的个数。至此,再没有哪个数字的个数可以由单个字母决定了。

那下面再看字母 s,它出现在 67 中,现在我们知道了 6 的个数,那么 7 的个数就可以由 s 的个数减去 6 的个数。同样的道理,字母 v 出现在 57 中,我们就可以得到 5 的个数等于 v 的个数减 7 的个数。

其他数字的都是同样的道理,这样我们可以得到下面的解法:

class Solution {
public:
string originalDigits(string s) {
vector<int> map(26, 0);
vector<int> count(10, 0);
for (auto ch : s) {
if (ch == 'z') count[0]++; // 0
if (ch == 'o') count[1]++; // 0, 1, 2, 4
if (ch == 'w') count[2]++; // 2
if (ch == 'r') count[3]++; // 0, 3, 4
if (ch == 'u') count[4]++; // 4
if (ch == 'f') count[5]++; // 4, 5
if (ch == 'x') count[6]++; // 6
if (ch == 'v') count[7]++; // 5, 7
if (ch == 'g') count[8]++; // 8
if (ch == 'i') count[9]++; // 5, 6, 8, 9
}
count[1] -= count[0] + count[2] + count[4]; // 1
count[3] -= count[0] + count[4]; // 3
count[5] -= count[4]; // 5
count[7] -= count[5]; // 7
count[9] -= count[5] + count[6] + count[8]; // 9
string ret;
for (int i = 0; i < 10; ++i) {
ret += string(count[i], i + '0');
}
return ret;
}
};

注释中的内容是数字的拆分,时间复杂度依然为 $O(n)$,但是不一样的地方在于,第二段代码只对输入字符串扫描了一遍。虽然复杂度是一样的,但是由于时间复杂度的计算是不包含前面的系数的,二者带来的差距其实还是存在的。

后记

这道题其实本身并不难,但是如果用很朴素的方法做,效率会相对较低。仔细观察数字对应英文的构造,还是可以得出更高效的算法来的。