題目描述

輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。

輸入描述:

輸入一個字符串,長度不超過9(可能有字符重復(fù)),字符只包括大小寫字母。

解法一：遞歸法

每一次遞歸負(fù)責(zé)將參數(shù)里的每一個字符輪流作為第一個字符，并和其余字符組成的序列結(jié)合構(gòu)成一個排列，return這些排列的list

from functools import reduce
class Solution:
    def Permutation(self,ss):
        if len(ss) == 0:
            return []
        elif len(ss) ==1:
            return ss
        elif len(ss) == 2:
            if ss[0]==ss[1]:
                return [ss]
            return [ss,ss[::-1]]
        else:
            return sorted(list(set(\
            reduce(lambda x,y:x+y,\
                      map(lambda i :[ss[i] + li\
                                    for li in self.Permutation(ss[:i]+ss[i+1:])],[i for i in range(len(ss))])))\
            ))

解法二，迭代法

n個元素的排列可由前n-1個元素的排列和第n個元素的排列求出
即 P(n) = f(P(n-1))
具體關(guān)系為，對于前n-1個元素的每一種排列，將第n個元素分別插入該排列下標(biāo)為0,1,2,,n-1的地方，得到對應(yīng)的n種新的排列，

class Solution:
    def Permutation(self,ss):
        if len(ss) == 0:
            return []
        elif len(ss) ==1:
            return ss
        elif len(ss) == 2:
            if ss[0]==ss[1]:
                return [ss]
            return [ss,ss[::-1]]
        else:
            res = self.Permutation(ss[:2])
            for ele in ss[2:]:
                new_strs = []
                for to_str in res:
                    for i in range(len(to_str)+1):
                         new_strs.append(to_str[:i] + ele + to_str[i:])
                res = new_strs

            return sorted(list(set(res)))