# 5-line O(N) solution, a pure math problem of vector equation (detailed explanation)

•     string originalDigits(string s) {
unordered_map<char, int> freq; for (char c:s) freq[c]++; // get frequency count for s
int count[10] = {freq['z'], freq['o']-freq['z']-freq['w']-freq['u'], freq['w'], freq['h']-freq['g'], // 0~3
freq['u'], freq['f']-freq['u'], freq['x'], freq['s']-freq['x'],                     // 4~7
freq['g'], freq['i']-freq['g']-freq['x']-freq['f']+freq['u']};                      // 8~9
string res; for (int i = 0; i < 10; i++) res += string(count[i], '0'+i); return res; // build result
}

The problem can be translated to a math problem of vector equation:

• Let 26-D vector sequence { wi=0:9 } be the char frequency vector of English words "zero" ~ "nine". for a given 26-D vector b, find solution { xi=0:9 } to solve vector equation
• Σi=0:9 xiwi = b. (assume it has a solution)

It is a 26-linear-equation system with only 10 variables which is usually over specified to have no solution, but the key is that the problem guarantees to have a solution.

Key observation:

1. Only unique vector, i.e., w0, w2, w6, w8 has 1 at component z, w, u, x, g, respectively; others have 0. So immediately we have solution of 5 components:
• x0 = b[z], x2 = b[w], x4 = b[u], x6 = b[x], x8 = b[g].
2. Look at components o, h, f, s, i of the vector equations, we have
• x0 + x1 + x2 + x4 = b[o],
• x3 + x8 = b[h],
• x4 + x5 = b[f],
• x6 + x7 = b[s],
• x5 + x6 + x8 + x9 = b[i].

Combining all equations above, we have the full solution:

• x0 = b[z],
• x1 = b[o] - b[z] - b[w] - b[u],
• x2 = b[w],
• x3 = b[h] - b[g],
• x4 = b[u],
• x5 = b[f] - b[u],
• x6 = b[x],
• x7 = b[s] - b[x],,
• x8 = b[g],
• x9 = b[i] - b[g] - b[x] - b[f] + b[u].

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