Java O(N) verbose&easy well-commented/explained


  • 0

    First, the code:

    class Solution {
        public String originalDigits(String s) {
            String[] digits = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
            char[] chs = s.toCharArray();
            if (s.length() < 3)
                return "";
            int[] counts = new int[26];     //counts of chars in s
            int[] order = {0,2,4,6,8,   3,5,7,      1,9};   //array of indices of digits to visit, ordered based on rarity of chars
            int[] res = new int[10];    //array to store and sort the result
            for (char c : chs)          //count chars in s
                counts[c - 'a']++;
            for (int i = 0; i < 10; i++) {
                int index = order[i];
                char[] chd = digits[index].toCharArray();
                int min = 50000;
                for (char c : chd) {
                    int count = counts[c - 'a'];
                    if ((i == 3 && c == 'e') ||
                        (i == 7 && c == 'e') ||
                        (i == 9 && c == 'n'))
                        count /= 2;
                    if (count < min)
                        min = count;
                }   //count is now the maximum number of copies of word_for_index we can extract from s
                if (min <= 0)   //abort if no copies available
                    continue;
                for (char c : chd)  //subtract char counts to reflect `min` copies extracted
                    counts[c - 'a'] -= min;
                res[index] += min;  //output to res
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < res[i]; j++) {
                    sb.append(i);
                }
            }
            return sb.toString();
        }
    }
    

    The idea is simple, consider one copy of each of the 0~9 words: "zeroonetwothreefourfivesixseveneightnine", we can counts the occurrence of each char and find out that:

    • z,x,w,u,g appears only 1 time;
    • v,s,h,f appears 2 times;
    • and the rest;

    We try to extract one word as many times as possible out of s (by subtracting this word's char counts out of s's counts) in each iteration.

    The key point is that, the ordering of the words to extract matters. We have to extract words with the rarest characters, i.e. the first case above first, and then words containing the second tier letters, then the rest. The array order is used for this purpose. With this idea in mind the code should be easy to relate to. The final loop does something you see in a bucket sort to pour out all the beans in order.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.