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"

只有10个数字的string， 因此可以穷举。
看到有一些数字有特殊独有的character

发现分三步就可以完成
1: zero， two，six，eight，four   除掉string s中的这些后可以做第二步
2. one，three，five, seven
3. nine，ten

因此需要1个size为3 的step map list存每个step map<Character,Integer>
除掉这步中算过的character 就从count map中删掉

   public String originalDigits(String s) {  
     List<Map<Character,Integer>> stepsMap = new ArrayList<>();      
     Map<Character,String> dict = new HashMap<>();   
     Map<Character,Integer> step1 = new HashMap<>();   
     step1.put('z',0);dict.put('z',"zero");  
     step1.put('w',2);dict.put('w',"two");  
     step1.put('u',4);dict.put('u',"four");  
     step1.put('x',6);dict.put('x',"ix");  
     step1.put('g',8);dict.put('g',"eight");  
     Map<Character,Integer> step2 = new HashMap<>();   
     step2.put('o',1);dict.put('o',"one");  
     step2.put('h',3);dict.put('h',"three");  
     step2.put('f',5);dict.put('f',"five");  
     Map<Character,Integer> step3 = new HashMap<>();   
     step3.put('v',7);dict.put('v',"seven");  
     step2.put('i',9);dict.put('i',"nine");  
     stepsMap.add(step1);stepsMap.add(step2);stepsMap.add(step3);  
     Map<Character,Integer> count = new HashMap<>();   
     for(int i = 0; i< s.length();i++){  
       char c = s.charAt(i);  
       count.putIfAbsent(c,0);  
       count.put(c,count.get(c)+1);  
     }  
     int[] digits = new int[10];  
     //3 steps  
     for(int i = 0; i < stepsMap.size(); i++){  
       Map<Character,Integer> step = stepsMap.get(i);  
       for(char c : step.keySet()){  
         if(count.containsKey(c)){  
           int occur = count.get(c);  
           digits[step.get(c)] = occur;  
           String str = dict.get(c);  
           for(int j = 0; j < str.length();j++){  
             char d = str.charAt(j);  
             count.put(d,count.get(d)-occur);  
             if(count.get(d) == 0)  
               count.remove(d);  
           }  
         }  
       }  
     }  
     StringBuilder sb = new StringBuilder();  
     for(int i = 0; i < 10; i++){  
       while(digits[i]-- >0)  
         sb.append(""+i);  
     }  
     return sb.toString();  
   }  

O(n) 1pass
按照计算顺序，统计相对特殊字符（10个）的出现次数
计算完上一步的特殊字符，例如知道0出现了两次，那么0 这个数字在cout 'o' 也出现了两次，从o的count中减去2

public String originalDigits(String s) {
    int[] count = new int[10];
    for (int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if (c == 'z') count[0]++;
        if (c == 'w') count[2]++;
        if (c == 'x') count[6]++;
        if (c == 's') count[7]++; //7-6
        if (c == 'g') count[8]++;
        if (c == 'u') count[4]++; 
        if (c == 'f') count[5]++; //5-4
        if (c == 'h') count[3]++; //3-8
        if (c == 'i') count[9]++; //9-8-5-6
        if (c == 'o') count[1]++; //1-0-2-4
    }
    count[7] -= count[6];
    count[5] -= count[4];
    count[3] -= count[8];
    count[9] = count[9] - count[8] - count[5] - count[6];
    count[1] = count[1] - count[0] - count[2] - count[4];
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i <= 9; i++){
        for (int j = 0; j < count[i]; j++){
            sb.append(i);
        }
    }
    return sb.toString();
}