首页 > 代码库 > [LeetCode] 423 Reconstruct Original Digits from English
[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:
- 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"
解法：原来的字符串是乱序的，当遇到一个字母 e 的时候，并没有办法知道这个字符是属于 one、three、nine等中的一个。但是当遇到一个 z 的时候，肯定
是可以确定这个字符是属于 zero 的，因为z只出现在zero中，同理，x 也只出现在six中。
那么这就是一个优先级的问题，应该优先匹配那些属于少数数字的字符，例如优先寻找z，如果出现一个z，那么必须相应的出现e、r、o。如果字符串里面已经没有z了，
那么这个时候如果还出现了r，那么这个 r 就只可能属于 three、four中的一个了，依次类推，就能得到解法。
for (char c : s.toCharArray()) { count[c]++; } int[] res = new int[10]; char[] idx = {‘z‘, ‘x‘, ‘s‘, ‘v‘, ‘f‘, ‘r‘, ‘w‘, ‘g‘, ‘o‘, ‘i‘}; //char[] idx = {‘z‘, ‘x‘, ‘s‘, ‘v‘, ‘f‘, ‘r‘, ‘w‘, ‘g‘, ‘o‘, ‘i‘}; for (char i : idx) { while (count[i] > 0) { switch (i) { case ‘z‘: //匹配z，减去zero res[0]++; count[‘z‘]--; count[‘e‘]--; count[‘r‘]--; count[‘o‘]--; break; case ‘x‘: //匹配six,减去six res[6]++; count[‘s‘]--; count[‘i‘]--; count[‘x‘]--; break; case ‘s‘: //匹配seven,因为之前优先匹配了six,如果这个时候,还有多余的s,那么肯定是seven res[7]++; count[‘s‘]--; count[‘e‘]--; count[‘v‘]--; count[‘e‘]--; count[‘n‘]--; break; case ‘v‘: //匹配five,因为之前优先匹配了seven,如果这个时候还出现v,那么肯定是属于five res[5]++; count[‘f‘]--; count[‘i‘]--; count[‘v‘]--; count[‘e‘]--; break; case ‘f‘: //匹配four,因为之前匹配了four,那么这个时候还出现f,那么肯定属于four res[4]++; count[‘f‘]--; count[‘o‘]--; count[‘u‘]--; count[‘r‘]--; break; case ‘r‘: //匹配three,因为之前匹配了four,还出现three,肯定属于three res[3]++; count[‘t‘]--; count[‘h‘]--; count[‘r‘]--; count[‘e‘]--; count[‘e‘]--; break; case ‘w‘: res[2]++; count[‘t‘]--; count[‘w‘]--; count[‘o‘]--; break; case ‘g‘: res[8]++; count[‘e‘]--; count[‘i‘]--; count[‘g‘]--; count[‘h‘]--; count[‘t‘]--; break; case ‘o‘: res[1]++; count[‘o‘]--; count[‘n‘]--; count[‘e‘]--; break; case ‘i‘: res[9]++; count[‘n‘]--; count[‘i‘]--; count[‘n‘]--; count[‘e‘]--; break; default: break; } } } //System.out.print(res[0]); StringBuilder sb = new StringBuilder(); for (int i = 0; i <= 9; i++) { for (int j = 0; j < res[i]; j++) { sb.append(i); } } return sb.toString(); }
[LeetCode] 423 Reconstruct Original Digits from English
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。