Formatted question description: https://leetcode.ca/all/423.html

423. Reconstruct Original Digits from English

Level

Medium

Description

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”

Solution

The number of occurrences for each letter does not change no matter how the order of letters changes, so count the number of occurrences for each letter in the given string.

Some words have letters that do not occur in other words, including “z” in “zero”, “w” in “two”, “u” in “four, “x” in “six”, and “g” in “eight”. Therefore, if one of the letters occur in the string, then the corresponding digit must occur. For each of the digits, find the maximum possible occurrences of the digit, which is determined by the letter only occuring in the digit’s word, append the digit to the result string, and reduce the number of occurrences of the letters accordingly.

After 0, 2, 4, 6, and 8 are figured out, there are other letters that occur in only one word, including “o” in “one”, “h”, “r” and “t” in “three”, “f” in “five” and “s” in “seven”. Do the steps above accordingly and append the digits to the result string.

After 1, 3, 5, 7 are figured out, there are only letters for digit 9, so count the number of occurrences of digit 9 using the remaining letters, and append the digit 9 to the result string according to the number of occurrences.

Finally, sort the result string and return.

class Solution {
    public String originalDigits(String s) {
        String[] wordsArray = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
        int[] numsInOrder = {0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
        int[] counts = new int[26];
        int length = s.length();
        for (int i = 0; i < length; i++)
            counts[s.charAt(i) - 'a']++;
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < 10; i++) {
            int num = numsInOrder[i];
            String word = wordsArray[num];
            int[] curCounts = new int[26];
            int wordLength = word.length();
            for (int j = 0; j < wordLength; j++)
                curCounts[word.charAt(j) - 'a']++;
            int digitCount = Integer.MAX_VALUE;
            for (int j = 0; j < 26; j++) {
                if (curCounts[j] > 0)
                    digitCount = Math.min(digitCount, counts[j] / curCounts[j]);
            }
            for (int j = 0; j < digitCount; j++)
                sb.append(num);
            for (int j = 0; j < 26; j++) {
                if (curCounts[j] > 0)
                    counts[j] -= curCounts[j] * digitCount;
            }
        }
        char[] digitsArray = sb.toString().toCharArray();
        Arrays.sort(digitsArray);
        return new String(digitsArray);
    }
}

All Problems

All Solutions