【剑指Offer】27.字符串的排列

题目描述

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

输入描述:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

解题思路

如何求出几个字符的所有排列，很多人都不能一下子想出解决方案，可以考虑把这个复杂的问题分解成小的问题。把一个字符串看成两部分组成：第一部分为它的第一个字符，第二部分是后面的所有字符。

求整个字符串的排列， 看成两步：首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。首先固定第一个字符，求后面所有字符的排列。仍然把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换。

递归的思路

Python代码

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        return sorted(set(self.PermutationHelp(ss)))
 
    def PermutationHelp(self, ss):
        if not ss:
            return []
        if len(ss) == 1:
            return list(ss)
        res = []
        for i in xrange(len(ss)):
            tmp = ss[:i] + ss[i + 1:]
            tail = self.PermutationHelp(tmp)
            for j in xrange(len(tail)):
                tail[j] = ss[i] + tail[j]
            res += tail
        return res