Python: short (8 lines) and clear


  • 0

    It's probably not as fast as the mathematical solutions, but I think that it is easier to understand. It is still O(n) (except for the final ordering which could be easily avoided) and is fast enough to pass OJ. Plus it can be easily adapted to properly handle invalid strings by checking if anything remains at the end in S.

    def originalDigits(self, s):
        numbers = [('zero',0),('two',2),('eight',8),('four',4),('one',1),('three',3),('five',5),('six',6),('seven',7),('nine',9)]
        res, S = [], collections.Counter(s)
        for n in numbers:
            c = collections.Counter(n[0])
            while c&S == c:
                res.append(n[1])
                S -= c
        return ''.join([str(i) for i in sorted(res)])
    

  • 0
    R

    @dalwise Nice solution!


  • 0
    Y
    This post is deleted!

  • 0
    Y

    I have a bad solution!
    I think I'm coding with C++.
    And can you tell me how to code like you?

    class Solution(object):
        def originalDigits(self, s):
            countAll = {}
            for c in s:
                if c in countAll.keys():
                    countAll[c] += 1
                else:
                    countAll[c] = 1
            mp = (('eight', 8), ('six', 6), ('two', 2), ('three', 3), ('zero', 0), ('seven', 7), ('five', 5), ('nine', 9), ('four', 4), ('one', 1))
            res = {}
            for t in mp:
                count = {}
                for c in t[0]:
                    if c in count.keys():
                        count[c] += 1
                    else:
                        count[c] = 1
                mn = 50000
                ok = True
                for key in count.keys():
                    if countAll.get(key) and count.get(key) and countAll[key] >= count[key]:
                        tmp = countAll[key] // count[key]
                        mn = (mn, tmp)[mn >= tmp]
                    else:
                        ok = False
                if not ok:
                    continue
                print(t[0], count, mn)
                print(countAll)
                for key in count.keys():
                    if countAll.get(key) and count.get(key):
                        countAll[key] -= count[key] * mn
                if t[1] in res.keys():
                    res[t[1]] += mn
                else:
                    res[t[1]] = mn
            r = ""
            for key in res.keys():
                for a in range(res[key]):
                    r += str(key)
            return r
    

  • 0
    S

    The biggest trick here is the ordering of list numbers. Disrupt that order and many test cases fail. Please add to your solution an explanation for this ordering choice.


Log in to reply
 

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