Skip to content

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

Solution 1

Thinking

English digit words overlap, so matching words in order is unsafe. A few letters belong to only one digit.

\(\texttt{z}\) is unique to zero, \(\texttt{w}\) to two, \(\texttt{u}\) to four, \(\texttt{x}\) to six, \(\texttt{g}\) to eight. After subtracting those, \(\texttt{h}\), \(\texttt{f}\), \(\texttt{s}\) give three, five, seven, and finally \(\texttt{o}\) and \(\textit{i}\) give one and nine.

Counting along that unique-letter order solves a triangular system; concatenate digits from \(0\) to \(9\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)
}

Comments