0數學/字元串中等 LeetCode423. 從英文中重建數字

423. 從英文中重建數字

描述

給你一個字元串 s ，其中包含字母順序打亂的用英文單詞表示的若幹數字（0-9）。按 升序 傳回原始的數字。

分析

有的“數字單詞”是可以通過一個字母的數量就能得知單詞出現的次數，有的需要多個字母一起推導才能得出，由此給數字排優先級，友善計算各個“數字單詞”出現的次數。

參考：

“宮水三葉”：https://leetcode-cn.com/problems/reconstruct-original-digits-from-english/solution/gong-shui-san-xie-nao-jin-ji-zhuan-wan-m-vg7a/

以及評論區的題解：

字元數組是可以排序的！

char[] ch = sb.toString().toCharArray(); Arrays.sort(ch);

可以将字元數組直接轉成字元串

String.valueOf(ch);

class Solution {
    public String originalDigits(String s) {
        Map<Character,Integer> map = new HashMap<>();
        String[] str = new String[]{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
        int[] priority = new int[]{0,6,2,4,8,7,3,5,1,9};
        StringBuffer sb = new StringBuffer("");
        //統計字元串s中的字母出現的次數
        for(int i = 0; i < s.length(); i++){
            if(map.containsKey(s.charAt(i))){
                map.put(s.charAt(i),map.get(s.charAt(i))+1);
            }else{
                map.put(s.charAt(i),1);
            }
        }
        //根據優先級先後計算“數字單詞”出現的次數
        for(int i : priority){
            int k = Integer.MAX_VALUE;
            //取較小值，最小的k一定代表這個單詞出現的次數
            for(int j = 0; j < str[i].length(); j++){
                k = Math.min(k,map.getOrDefault(str[i].charAt(j),0));
            }
            //從Map中減去這個單詞對應的字母出現的次數
            for(int j = 0; j < str[i].length(); j++){
                int deduct = map.getOrDefault(str[i].charAt(j),0) - k;
                map.put(str[i].charAt(j),deduct);
            }
            //出現了k次是以要加入k次i
            while(k > 0){
                sb.append(i);
                k--;
            }
        }
        //題目要求按由小到大的順序排序。字元數組是可以排序的！可以将字元數組直接轉成字元串
        char[] ch = sb.toString().toCharArray();
        Arrays.sort(ch);
        return String.valueOf(ch);
    }
}