Short Matrix Solution


  • 7

    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
    

  • 0
    C

    @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])])
    
    

Log in to reply
 

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