给你一个字符串 s ,其中包含字母顺序打乱的用英文单词表示的若干数字(0-9)。按 升序 返回原始的数字。
示例 1:
输入:s = "owoztneoer" 输出:"012" 示例 2:
输入:s = "fviefuro" 输出:"45"
提示:
1 <= s.length <= 105 s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一 s 保证是一个符合题目要求的字符串
题解: 这种题还是非常有意思的,主要在于它很好想,先把这十个英语单词列出来,然后抽丝剥茧一样的先提取出能唯一确定一个单词的字母,比如0(zero)里面的z是十个单词中独有的……
class Solution {
public:
string originalDigits(string s) {
unordered_map<char, int> m;
for(auto e: s){
m[e]++;
}
string ans;
int cnt = s.size();
while(cnt){
while(m['z']){
m['z']--;
m['e']--;
m['r']--;
m['o']--;
cnt -= 4;
ans += '0';
}
//cout<<"cnt1:"<<cnt<<endl;
while(m['w']){
m['t']--;
m['w']--;
m['o']--;
cnt -= 3;
ans += '2';
}
//cout<<"cnt2:"<<cnt<<endl;
while(m['u']){
m['f']--;
m['o']--;
m['u']--;
m['r']--;
cnt -= 4;
ans += '4';
}
//cout<<"cnt3:"<<cnt<<endl;
while(m['g']){
m['e']--;
m['i']--;
m['g']--;
m['h']--;
m['t']--;
cnt -= 5;
ans += '8';
}
//cout<<"cnt4:"<<cnt<<endl;
while(m['x']){
m['s']--;
m['i']--;
m['x']--;
cnt -= 3;
ans += '6';
}
//cout<<"cnt5:"<<cnt<<endl;
while(m['r']){
m['t']--;
m['h']--;
m['r']--;
m['e'] -= 2;
cnt -= 5;
ans += '3';
}
//cout<<"cnt6:"<<cnt<<endl;
while(m['f']){
m['f']--;
m['i']--;
m['v']--;
m['e']--;
cnt -= 4;
ans += '5';
}
//cout<<"cnt7:"<<cnt<<endl;
while(m['o']){
m['o']--;
m['n']--;
m['e']--;
cnt -= 3;
ans += '1';
}
//cout<<"cnt8:"<<cnt<<endl;
while(m['v']){
m['s']--;
m['e'] -= 2;
m['v']--;
m['n']--;
cnt -= 5;
ans += '7';
}
//cout<<"cnt9:"<<cnt<<endl;
while(m['i']){
m['n'] -= 2;
m['i']--;
m['e']--;
cnt -= 4;
ans += '9';
}
//cout<<"cnt10:"<<cnt<<endl;
}
sort(ans.begin(), ans.end());
return ans;
}
};
官方题解给出的代码看上去更加简洁漂亮一点,要学呀!
class Solution {
public:
string originalDigits(string s) {
unordered_map<char, int> c;
for (char ch: s) {
++c[ch];
}
vector<int> cnt(10);
cnt[0] = c['z'];
cnt[2] = c['w'];
cnt[4] = c['u'];
cnt[6] = c['x'];
cnt[8] = c['g'];
cnt[3] = c['h'] - cnt[8];
cnt[5] = c['f'] - cnt[4];
cnt[7] = c['s'] - cnt[6];
cnt[1] = c['o'] - cnt[0] - cnt[2] - cnt[4];
cnt[9] = c['i'] - cnt[5] - cnt[6] - cnt[8];
string ans;
for (int i = 0; i < 10; ++i) {
for (int j = 0; j < cnt[i]; ++j) {
ans += char(i + '0');
}
}
return ans;
}
};