100ms in Python


  • 1
    A

    This solution is the fastest of the histogram, so I thought of sharing it here.
    It's a pretty straightforward recursive solution, keeping track of the elements that have already been used, and passing it around in a hashtable (dictionnary) in order to efficiently treat the cases of multiple equal elements.
    I use a defaultdict(int) to initialize by default the elements of the hashtable as a zero integer.
    Enjoy !

    class Permuter:
        def __init__(self, basis):
            self.basis = basis
            self.L = len(basis)
            self.permutations = []
            self.elts = collections.defaultdict(int)
            for elt in self.basis:
                self.elts[elt] += 1
             
        def getPermutations(self):
            self.growPermutations([0]*self.L, self.elts, 0)
            return(self.permutations)
             
        def growPermutations(self, permuted, elts, current):
            if current == self.L-1:
                for elt, num in elts.iteritems():
                    if num:
                        permuted[current] = elt
                        self.permutations.append(permuted)
                        break
            else:
                for elt, num in elts.iteritems():
                    if num:
                        permutedi = permuted[:]
                        permutedi[current] = elt
                        elts[elt] -= 1
                        self.growPermutations(permutedi, elts, current+1) 
                        elts[elt] += 1
                    
    
    class Solution:
        # @param num, a list of integer
        # @return a list of lists of integers
        def permuteUnique(self, num):
            pp = Permuter(num)
            return pp.getPermutations()

  • 0
    R

    How did you figure out that you can use collections, without "import collections"?! That is unfair. :-)

    I tried "import whatever" before and it always results in compile error on this leetcode platform.


Log in to reply
 

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