【劍指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