28、字符串的全排列

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

我们可以考虑把复杂的问题分解成小的问题。

比如在递归求以a开头的排列时，分成两步

• 第一步：把此字符串分成两部分，第一部分是字符a，第二部分是字符bc。接下来递归求第二部分字符串bc的排列。
  在递归到bc时，会首先按照第一步把bc分成两部分，对c递归调用函数。然后对c后面进行调用递归函数时返回c，然后返回上一个递归函数返回bc。接着第二步会把b与后面的字符逐个交换，成cb，然后返回cb。
• 第二步：把第一个字符a与它后面的字符逐个交换。比如交换成bac，cab，然后再进行递归调用。

需要注意的事情：
如果按照每次递归只返回一个字符串的话，那么肯定是不可取得。
比如，对于首字母为“a”的字符串，第二部分应该返回的是“bc”，“cb”。而如果只返回一个“bc”，那么结果肯定就不准确了。

因此，这里我在递归函数最开始初始化了一个res列表，用来返回此次调用递归函数的结果。比如，对于“bc”传入递归函数，

• 第一个for循环，当首字母为“b”时，
• 接下来的for会调用递归函数，把第二部分“c”传入递归函数，
• 然后递归函数会返回一个列表["c"]，然后此时递归函数调用结束。
• 接下来会在res中添加进“bc”,
• 对于首字母为“c”时，最终res会添加进“cb”，
• 因此，最终res列表会返回["bc","cb"]。

那么，当abc传入时，首字母为a时，会把bc传入，然后字符串a会与bc和cb相加。首字母为b时，会。。。

注意，会出现字符串重复的情况，因此这里要判重。

代码实现：
如果对于代码中，递归怎样调用，以及递归的停止条件有疑问，举个例子试试就行了。比如这里举例当bc传入时，怎么返回一个["bc","cb"]，按照上面思想，首字母传入以后，就知道应该判定当第二部分长度为1时，返回第二部分了。

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        res = []
        #如果ss为空，那么就返回一个空列表
        if len(ss) == 0:
            return []
        if len(ss) == 1:
            return ss
        #确定此时字符串的首字母
        for i in range(len(ss)):
            #把字符串的第二部分传入递归函数中，
            # 对递归函数返回的结果进行遍历，用于与首字母相加
            for out in self.Permutation(ss[0:i] + ss[i+1:]):
                res_pre = ss[i] + out
                #对于字符串中有重复的情况，需要用下面语句去重
                #如果直接在结果中用set去重，会导致结果看起来比较乱，不如判重比较合适
                if res_pre not in res:
                    res.append(res_pre)
        return res

S = Solution()
print(S.Permutation('aabcd'))