Python solution, beats 99.67%


  • 32
    class Solution(object):
        def maxProduct(self, words):
            d = {}
            for w in words:
                mask = 0
                for c in set(w):
                    mask |= (1 << (ord(c) - 97))
                d[mask] = max(d.get(mask, 0), len(w))
            return max([d[x] * d[y] for x in d for y in d if not x & y] or [0])

  • 0
    Z

    Nice solution. Instead of sorting the original word list, what I did was:

    class Solution(object):
        def maxProduct(self, words):
    :::
            test = {}
            for w in words: 
                tmp = 0x0
                for ch in set(w):
                    tmp |= (0x1 << (ord(ch) - 97))            
                test[tmp] = max(test.get(tmp, 0), len(w))
    :::
    

    This beats around 99.63%. Sometimes, sorting is expensive.


  • 0
    R

    I don't know why, i paste ur answer to the solution, it said time limit exceeded,


  • 2
    T

    It would be better if you replace 97 with ord('a') to avoid magic numbers.


  • 0
    R

    Nice code! But why << and & fast? Because of hardware?


  • 0
    T

    @rw1993 Direct bit manipulations are usually faster because less translations from normal operations to bit manipulations are involved


  • 0

    Good solution!

    You could slightly shorten it like this:

        def maxProduct(self, words):
            d = {}
            for w in words:
                mask = reduce(operator.or_, (1 << (ord(c)-97) for c in set(w)), 0)
                d[mask] = max(d.get(mask, 0), len(w))
            return max([d[a]*d[b] for a in d for b in d if not (a & b) ] or [0])
    

    Or even use "sum" instead of "or" as in other solutions.


  • 0

    nice and clean, thanks for sharing


  • 0

    said in Python solution, beats 99.67%:

    [0]

    Every time I can learn a lot from your code! Cool!


  • 0
    S

    beautiful~~~~


Log in to reply
 

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