Python + Numpy matrix solution (Do it like a scientist!)


  • 0
    P

    I used a two-liner to generate the matrix A, whose [i, j]element (count from zero) is vector representing how many times a letter letter[j] appears in the English word for i, and letter[0] == a For example, the first list (A0) says there are1 E, 1 O, 1 R and 1 Z in "zero".

    Vector b is the above quantity for the target string. Now we need to solve the equation
    A0.x0 + A1.x1 + ... + A9.x9 = b, where x0...x9 are numbers for counting the numerals.
    Combining the above equations we get
    Transpose(A) . X = b
    here X is a vector of (x0, x1, ..., x9)
    To get the inverse of a non-square matrix, numpy has a pseudoinverse (pinv) for that. Due to the numerical error, the answer is a close-to-integer float, so some nasty cropping is needed.

    import numpy as np
    
    class Solution:
        def originalDigits(self, s):
            A = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
            b = [0 for i in range(26)]
            for c in s:
                b[ord(c) - ord('a')] += 1
            x = np.dot(np.linalg.pinv(np.transpose(A)), b)
            x = [int(round(i)) for i in x]
            res = ""
            for i in range(10):
                res += str(i) * x[i]
            return res
    

Log in to reply
 

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