# Short Matrix Solution

• Solution

``````def original_digits(s)
require 'matrix'
a = ('a'..'z').map { |c| "zero one two three four five six seven eight nine".split.map { |w| w.count(c) } }
b = ('a'..'z').map { |c| s.count(c) }
x = Matrix[*a].lup.solve(b)
(0..9).map { |i| i.to_s * x[i] }.join
end
``````

Explanation

Using Ruby's `Matrix` class to solve the system of equations. We have one equation for each letter. For example, consider the letter 'n'. If the unknown digits are x0 zeros, x1 ones, etc, then the letter 'n' appears x1 + x7 + 2x9 times. Each "one" or "seven" contributes one 'n', each "nine" contributes two 'n', and the other digits don't contribute any 'n'. Now for example if the input is `s = "owoztneoer"` then we have one 'n' and thus we have the equation x1 + x7 + 2x9 = 1. Doing this for all 26 letters gives us 26 equations which we can write as a matrix equation `Ax = b`.

• `A` is the 26×10 matrix with ai,j telling how often the i-th alphabet letter appears in the j-th digit name.
• `b` is the vector of size 26 with bi telling how often the i-th alphabet letter appears in the given `s`.
• `x` is the vector of size 10 with xi telling how often the i-th digit is encoded in the given `s`.

Alternatives

Since `A` is always the same (doesn't depend on `s`), we can precompute it so it doesn't get computed every time our function is called:

``````require 'matrix'
A = ('a'..'z').map { |c| "zero one two three four five six seven eight nine".split.map { |w| w.count(c) } }
Solve = Matrix[*A].lup.method(:solve)

def original_digits(s)
x = Solve[('a'..'z').map { |c| s.count(c) }]
(0..9).map { |i| i.to_s * x[i] }.join
end
``````

Could even make the actual function a one-liner then:

``````def original_digits(s)
Solve[('a'..'z').map { |c| s.count(c) }][0..9].map.with_index { |x, i| i.to_s * x }.join
end
``````

• @StefanPochmann really like your solution;)
Python version:

``````class Solution(object):
def originalDigits(self, s):
"""
:type s: str
:rtype: str
"""
import numpy as np
import string
import math
alphaes = string.ascii_lowercase[:26]
num_list = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']
A = []
for alpha in alphaes:
a = []
for num in num_list:
a.append(num.count(alpha))
A.append(a)
b = []
for alpha in alphaes:
b.append(s.count(alpha))
A = np.array(A)
b = np.array(b)
return ''.join([int(round(item)) * str(index) for index, item in enumerate(np.linalg.lstsq(A, b)[0])])

``````

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