Python O(N) solution


  • 0
    S

    Use the fact that all even numbers have unique char. Then count the remaining numbers by subtracting the already counted ones.

    def originalDigits(self, s):
        count = [ 0 for _ in range(10)]
        for c in s:
            # numbers with unique char
            if c == 'z':
                count[0] += 1
            if c == 'w':
                count[2] += 1
            if c == 'x':
                count[6] += 1
            if c == 'g':
                count[8] += 1
            if c == 'u':
                count[4] += 1
            # numbers derived from others:
            if c == 'f':
                count[5] += 1
            if c == 'h':
                count[3] += 1
            if c == 's':
                count[7] += 1
            if c == 'o':
                count[1] += 1
            if c == 'i':
                count[9] += 1
    
        count[5] -= count[4]
        count[3] -= count[8]
        count[7] -= count[6]
        count[1] -= (count[0] + count[2] + count[4])
        count[9] -= (count[5] + count[6] + count[8])
    
        result = []
        for i in range(10):
            for j in range(count[i]):
                result.append(i)
    
        return ''.join(str(num) for num in result)
    

    '''


Log in to reply
 

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