leetcode剣指Offer 38.文字列の配置

剣指Offer 38.文字列の配置文字列を入力し、その文字列内の文字のすべての配置を印刷します.
この文字列配列は任意の順序で返すことができますが、重複要素はありません.
例:
入力:s=「abc」出力:[「abc」,「acb」,「bac」,「bca」,「cab」,「cba]]
制限:
1<=sの長さ<=8
遡及の使用を開始しますが、セットが適用されないとタイムアウトします.

class Solution:
    def permutation(self, s: str) -> List[str]:
        if not s: return [""]
        out = set()#     ，        
        def backtrack(s,  res):
            if not s:
                out.add(res)
            for i in range(len(s)):
                backtrack(s[:i]+s[i+1:], res + s[i])

        backtrack(s, "")
        # out = out.sort()
        return list(out)

重複スキーマと枝切り:文字列に重複文字がある場合、配列スキーマにも重複スキーマがあります.重複スキームを排除するには、ある文字を固定するときに、「各文字はこのビットに1回しか固定されていない」ことを保証する必要があります.つまり、重複文字に遭遇したときに交換せず、直接スキップします.DFSの観点から、この操作を「枝切り」と呼ぶ.
しかし、上記の方法では動作が遅く、重複する文字がスキップできないという問題があります.たとえば、次のようにします.

[a,a,b] 

最初のaを先頭文字として開始すると、2番目のaが出力文字列に追加されます.しかし、2番目のaをはじめとする文字の場合、以降のすべての組み合わせは前回計算されているので、これ以上計算する必要はありません.これが枝を切ることができる場所です.次のプログラムは、元の文字列を文字ソートし、現在の文字が前の文字と同じであれば、枝を切ってスキップします.

class Solution:
    def permutation(self, s: str) -> List[str]:
        if not s: return [""]
        s = [s[i] for i in range(len(s))]
        sorted_s = sorted(s)
        out = []

        def backtrack(s, res):
            if not s:#            
                out.append(res)
            for i in range(len(s)):
                if i > 0 and s[i] == s[i-1]:#       
                    continue
                else:
                    backtrack(s[:i]+s[i+1:], res+s[i])
        backtrack(sorted_s, "")
        return out
        

やはり大物の考えを見てみましょう:ここの枝を切って私たちは先にソートしないで、1つの集合の記録の前に誰が使った文字を作って、もし重複する文字が現れたら、スキップして、1つのソートを少なくして、隣接するメタ数の比較の過程.

class Solution:
    def permutation(self, s: str) -> List[str]:
        self.res = []
        n = len(s)

        def backtrack(s, path):
            if not s:
                self.res.append(path)
            seen = set()
            for i in range(len(s)):
                if s[i] in seen: continue
                seen.add(s[i])
                backtrack(s[:i]+s[i+1:], path + s[i])

        backtrack(s, "")
        return self.res