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


  • 0
        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].

Log in to reply
 

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