Welcome to Subscribe On Youtube

423. Reconstruct Original Digits from English

Description

Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order.

 

Example 1:

Input: s = "owoztneoer"
Output: "012"

Example 2:

Input: s = "fviefuro"
Output: "45"

 

Constraints:

• 1 <= s.length <= 105
• s[i] is one of the characters ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"].
• s is guaranteed to be valid.

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public String originalDigits(String s) {
          int[] counter = new int[26];
          for (char c : s.toCharArray()) {
              ++counter[c - 'a'];
          }
          int[] cnt = new 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];
  
          StringBuilder sb = new StringBuilder();
          for (int i = 0; i < 10; ++i) {
              for (int j = 0; j < cnt[i]; ++j) {
                  sb.append(i);
              }
          }
          return sb.toString();
      }
  }
  

• 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;
      }
  };
  

• 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))
  
  

• 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)
  }
  

All Problems

All Solutions