LeetCode 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:
- Input contains only lowercase English letters.
- 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.
- Input length is less than 50,000.
Example 1:
Input: "owoztneoer"
Output: "012"
Example 2:
Input: "fviefuro"
Output: "45"
给定一个用英文单词表示数字的字符串，要求恢复出这个数字字符串，英文字符串是被打乱了的。
这题纯粹是个找规律的题，先写出10个数字的英文单词，然后找找那个字符是每个单词特有的字符，比如可以确定的有：
找完上述5个单词之后，剩下的5个单词中每个单词特有的字符为：
所以我们首先找到字符和频率的对应关系，然后根据上面的顺序依次减掉相应单词的频率，并把数字放到结果数组中，最后从结果数组中构建结果字符串。完整代码如下：
[cpp]
class Solution {
public:
string originalDigits(string s) {
vector<int> hash(26, 0);
vector<int> digits(10, 0);
for (int i = 0; i < s.size(); ++i) {
++hash[s[i] – ‘a’];
}
while (hash[‘z’ – ‘a’]) { // 0
++digits[0];
–hash[‘z’ – ‘a’];
–hash[‘e’ – ‘a’];
–hash[‘r’ – ‘a’];
–hash[‘o’ – ‘a’];
}
while (hash[‘w’ – ‘a’]) { // 2
++digits[2];
–hash[‘t’ – ‘a’];
–hash[‘w’ – ‘a’];
–hash[‘o’ – ‘a’];
}
while (hash[‘u’ – ‘a’]) { // 4
++digits[4];
–hash[‘f’ – ‘a’];
–hash[‘o’ – ‘a’];
–hash[‘u’ – ‘a’];
–hash[‘r’ – ‘a’];
}
while (hash[‘x’ – ‘a’]) { // 6
++digits[6];
–hash[‘s’ – ‘a’];
–hash[‘i’ – ‘a’];
–hash[‘x’ – ‘a’];
}
while (hash[‘g’ – ‘a’]) { // 8
++digits[8];
–hash[‘e’ – ‘a’];
–hash[‘i’ – ‘a’];
–hash[‘g’ – ‘a’];
–hash[‘h’ – ‘a’];
–hash[‘t’ – ‘a’];
}
while (hash[‘o’ – ‘a’]) { // 1
++digits[1];
–hash[‘o’ – ‘a’];
–hash[‘n’ – ‘a’];
–hash[‘e’ – ‘a’];
}
while (hash[‘t’ – ‘a’]) { // 3
++digits[3];
–hash[‘t’ – ‘a’];
–hash[‘h’ – ‘a’];
–hash[‘r’ – ‘a’];
–hash[‘e’ – ‘a’];
–hash[‘e’ – ‘a’];
}
while (hash[‘f’ – ‘a’]) { // 5
++digits[5];
–hash[‘f’ – ‘a’];
–hash[‘i’ – ‘a’];
–hash[‘v’ – ‘a’];
–hash[‘e’ – ‘a’];
}
while (hash[‘s’ – ‘a’]) { // 7
++digits[7];
–hash[‘s’ – ‘a’];
–hash[‘e’ – ‘a’];
–hash[‘v’ – ‘a’];
–hash[‘e’ – ‘a’];
–hash[‘n’ – ‘a’];
}
while (hash[‘i’ – ‘a’]) { // 9
++digits[9];
–hash[‘n’ – ‘a’];
–hash[‘i’ – ‘a’];
–hash[‘n’ – ‘a’];
–hash[‘e’ – ‘a’];
}
string ans = "";
for (int i = 0; i < 10; i++) {
ans += string(digits[i], ‘0’ + i);
}
return ans;
}
};
[/cpp]
本代码提交AC，用时26MS。]]>