面试题38： 字符串的排列

题目：
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:字符串长度不超过9(可能有字符重复),字符只包括大小写字母

思路：
本题需要将问题分解，分别为确定第一个字符和除此之外的字符串的排列情况，而除第一个字符之外的字符串的排列结果可以递归实现。具体如下：

38 字符串的排列.png

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        #利用递归的思想

        listss = list(ss)
        Ptr = []
        listss.sort()
        #递归结束条件
        if len(listss) == 0:         #返回空
            return []
        if len(listss) == 1:         #如果只有一个字符，则返回这个字符组成的列表
            return list(listss) 

        for i in range(len(listss)):       #第一个位置的字符的可能性
            if i>0 and listss[i-1] == listss[i]:   #因为字符列表是有序的，所以相等的话直接跳过下面部分
                continue
            temp = self.Permutation(''.join(listss[:i]) + ''.join(listss[i+1:]))  #递归得到除第一个字符之外的组合

            for j in temp:
                Ptr.append(listss[i] + j)    #拼接

        return Ptr

提交结果：