Welcome to Subscribe On Youtube
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:
- 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”
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); } } -
class Solution: def originalDigits(self, s: str) -> str: counter = Counter(s) cnt = [0] * 10 cnt[0] = counter['z'] cnt[2] = counter['w'] cnt[4] = counter['u'] cnt[6] = counter['x'] cnt[8] = counter['g'] cnt[3] = counter['h'] - cnt[8] cnt[5] = counter['f'] - cnt[4] cnt[7] = counter['s'] - cnt[6] cnt[1] = counter['o'] - cnt[0] - cnt[2] - cnt[4] cnt[9] = counter['i'] - cnt[5] - cnt[6] - cnt[8] return ''.join(cnt[i] * str(i) for i in range(10)) ############ nums = {0: "zero", 1: "one", 2: "two", 3: "three", 4: "four", 5: "five", 6: "six", 7: "seven", 8: "eight", 9: "nine", 10: "ten"} feature = {0: "z", 1: "o", 2: "w", 3: "r", 4: "u", 5: "v", 6: "x", 7: "s", 8: "g", 9: "i", 10: "t"} class Solution(object): def originalDigits(self, s): """ :type s: str :rtype: str """ global nums, feature ans = [] count = {} for c in s: count[c] = count.get(c, 0) + 1 for num in [0, 2, 4, 6, 8, 1, 3, 7, 5, 10, 9]: featureNum = count.get(feature[num], 0) if featureNum > 0: ans += [str(num)] * featureNum word = nums[num] for c in word: count[c] -= featureNum ans.sort() return "".join(ans) -
class Solution { public: string originalDigits(string s) { vector<int> counter(26); for (char c : s) ++counter[c - 'a']; vector<int> cnt(10); cnt[0] = counter['z' - 'a']; cnt[2] = counter['w' - 'a']; cnt[4] = counter['u' - 'a']; cnt[6] = counter['x' - 'a']; cnt[8] = counter['g' - 'a']; cnt[3] = counter['h' - 'a'] - cnt[8]; cnt[5] = counter['f' - 'a'] - cnt[4]; cnt[7] = counter['s' - 'a'] - cnt[6]; cnt[1] = counter['o' - 'a'] - cnt[0] - cnt[2] - cnt[4]; cnt[9] = counter['i' - 'a'] - cnt[5] - cnt[6] - cnt[8]; string ans; for (int i = 0; i < 10; ++i) for (int j = 0; j < cnt[i]; ++j) ans += char(i + '0'); return ans; } }; -
func originalDigits(s string) string { counter := make([]int, 26) for _, c := range s { counter[c-'a']++ } cnt := make([]int, 10) cnt[0] = counter['z'-'a'] cnt[2] = counter['w'-'a'] cnt[4] = counter['u'-'a'] cnt[6] = counter['x'-'a'] cnt[8] = counter['g'-'a'] cnt[3] = counter['h'-'a'] - cnt[8] cnt[5] = counter['f'-'a'] - cnt[4] cnt[7] = counter['s'-'a'] - cnt[6] cnt[1] = counter['o'-'a'] - cnt[0] - cnt[2] - cnt[4] cnt[9] = counter['i'-'a'] - cnt[5] - cnt[6] - cnt[8] ans := []byte{} for i, c := range cnt { ans = append(ans, bytes.Repeat([]byte{byte('0' + i)}, c)...) } return string(ans) }