LeetCode "46. Permutations"をPythonで解いた話

問題

整数の配列numsが与えられています。それぞれの整数は1個ずつしかありません。ありうるすべての順列を答えてください。答えは、好きな順番で大丈夫です。

こちらから挑戦できます。
https://leetcode.com/problems/permutations/

方針

ライブラリーを使ってはいけないという注意書きがないので、itertoolsを使います。

from itertools import permutations

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return permutations(nums, len(nums))

結果:Success

やったぜ！

おまけ：itertoolsを使わないで解けるか？

方針：
queueを使って全探索をします。
同じ個所を2回以上探索しないように、足跡を集合で管理します。

import queue

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 1:
            return [nums]

        wake = set()
        comp = set()
        set_nums = set(nums)
        len_nums = len(nums)

        q = queue.Queue()

        for num in nums:
            q.put(tuple([num]))

        while not q.empty():

            cur = q.get()
            set_cur = set(cur)
            uncharted_nums = set_nums - set_cur

            for num in uncharted_nums:
                candidate = cur + tuple([num])

                if len_nums == len(candidate):
                    comp.add(candidate)
                    continue

                if candidate not in wake:
                    wake.add(candidate)
                    q.put(candidate)

        return list(comp)

結果:Success

やったぜ！