剣指offer JZ 27文字列の配列Python多解

一.タイトルの説明
文字列を入力し、その文字列のすべての配列を辞書順に印刷します.例えば文字列abcを入力すると、文字a,b,cで並べられるすべての文字列abc,acb,bac,bca,cab,cbaが印刷される.
説明を入力:
9を超えない文字列を入力します(文字が重複する可能性があります)、文字には大文字と小文字のみが含まれます.
二.問題を解く構想.
1.再帰+dfs
深度優先検索.
本題の出力には辞書順の出力が必要であることに注意してください.
文字列の全配列を辞書順で取得するにはどうすればいいですか?
私たちはこのように考えることができます.
文字列sがn長であると仮定すると、sに基づく2〜nビットのサブ文字列の全配列が知られており、2〜nビットの文字列の全配列の要素の先頭に最初の文字(仮定ビットa)を加算すると、文字列sの全配列の中でaで始まるすべての配列が得られる.
次に、文字列sの2番目の文字を1番目の文字とし、1番目の文字を2番目の文字とし、s[2]で始まる文字列sのすべての全配列にすることもできます.
すべての可能なs文字を先頭とすると、元の最初の要素と交換された要素との間の要素は、「abcde」のような交換された要素の後ろに順位に移動する.
cを先頭にすると、cとbcdeの全配列が組み合わされ、sの全配列が得られる(文字列sのサブ列2〜nの全配列があると仮定することに注意).
なぜ順番に対応する文字と最初の文字を置き換えるのか、問題は辞書順に出力することを要求しているからです.
元の文字列sが辞書シーケンスであり、サブ文字列の全配列も辞書シーケンスである場合、このようにして、私たちの結果も辞書シーケンスであることを保証することができる.
さて、2〜nの文字列の全配列が既知であると仮定すると、2〜nの文字列をどのように求めるか.
これにより,我々が再帰に用いる繰返し式が得られる.
同様の方法で,3~n,4~nの繰返しを得ることができる.
再帰の終了条件は、文字列の末尾、すなわち空の列に再帰することであり、返されると見なされる.
詳しくはコードを見て自分で消化してください.
再帰法には多くの繰り返し演算がある.例えばbcdeとacdeの全配列を計算する場合,cdeの全配列を計算する必要がある.もちろん、空間で時間を変えて、データ構造ですべての中間結果を保存することができますが、メモリが爆発する可能性があります.
時間複雑度:O(
2.動的計画
現在、ダイナミックプランニングは非ディクショナリシーケンス出力にのみ適用されます.
上の考えと似ていますが、ちょっと違います.ダイナミックプランニングは下から上へ.
動的計画では,1〜iビット目のサブ列の全伴配列があると仮定し,1〜i+1文字列の全配列をどのように計算するかを計算する.
i+1文字目を1〜iの全配列の各要素の可能なすべての挿入位置に挿入することは容易に考えられる.
前後の2つの位置の全配列を保存するだけなので,空間的複雑さも許容できる.
しかし、なぜ辞書順に出力できないのですか?
前の0~iの全配列を辞書順とする.
私は全配列のすべての要素を遍歴し、すべての可能な位置を挿入しているので、元の全配列の結果が秩序であっても、挿入位置はこの秩序状態を乱します.
例えば、
[ab,ba],今私はcを挿入して、挿入が最初から最後までと仮定して、結果は[cab,acb,abc,cba,bca,bac]であるべきです.
末尾から頭を挿入すると、結果は[abc,acb,cab,bac,bca,cba]であるべきである.
明らかに秩序から無秩序状態に変わった.
これは,あるビットに要素を挿入すると,このビットが他の解のビットの辞書順と比較される大きさが変化するためである.
時間複雑度O(N*N*N)
3.再帰+遡及
1とあまり違わない考え.
参考:牛客網遡及
三.ソースコード

# 1
class Solution:
    def Permutation(self, ss):
        # write code here
        if not ss:return []
        rst=[]
        existed=set()
        for i in range(len(ss)):
            temp=self.Permutation(ss[:i]+ss[i+1:])
            if not temp:return [ss[i]]
            for s in temp:
                if s not in existed:
                    rst.append(ss[i]+s)
                    existed.add(s)
        return rst

# 2   ac，          
class Solution:
    def Permutation(self, ss):
        # write code here
        if not ss:return []
        cur,last=[],['']
        for i in range(len(ss)):
            existed=set()
            for s in last:
                for k in range(len(last[0])+1):
                    new_s=s[:k]+ss[i]+s[k:]
                    if new_s not in existed:
                        cur.append(new_s)
                        existed.add(new_s)
            last,cur=cur,[]
        return last