题解 | #字符串的排列#

解题思路：
对于已有的每一种排列的每个位置k，插入第i个新数字ss[i]，得到一组新排列
详见注释
#=============================================================================================
'''

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here        
        n = len(ss)
        if n<=0:
            return
        if n==1:
            return ss

        ss = list(ss)                           # 输入转成list（list才有insert方法）
        out = []
        out.append([ss[0]])                     # i-1时已有的排列（二维数组）
        for i in range(1,n):
            tmp = []
            for string in out:                  # 对于已有的每一种排列
                for k in range(len(string)+1):  # 当前排列的每个位置k
                    s = string.copy()            # 复制当前排列
                    s.insert(k,ss[i])            # 在复制排列的第k个位置，插入第i个数ss[i]
                    tmp.append(s)                # 得到一组新排列加入临时二维数组
            out = tmp                           # 更新i-1时已有的排列

        for i in range(len(out)):
            out[i] = ''.join(out[i])            # 数组合成一个对象用于set()去重，再排序
        out = sorted(set(out))                  # set的元素只能是单个变量，不能是数组等多变量对象
        #print(out)
        return out

s = Solution()
ss = '121'  # ['ab','ba']
print(s.Permutation(ss))