剑指offer--面试题28：字符串的排列

题目描述

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

输入描述:

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

python实现：

# -*- coding:utf-8 -*- class Solution:     def Permutation1(self, ss):         # write code here         #可能有重复字母         n = len(ss)         if n==0:             return []         result = []         self.getPermutation1(ss, result, [], n)         #result.sort()         return result               def getPermutation(self, ss, result, tmpResult, n):         if len(tmpResult)==n:             result.append("".join(tmpResult))             return         #为避免结果集中有重复的排列（因为有重复字母），那么在选排列起点时就要去掉重复         for ch in sorted(set(ss)):#结果请按字母顺序输出             tmpResult.append(ch)             idx = ss.index(ch)             self.getPermutation1(ss[:idx]+ss[idx+1:], result, tmpResult, n)             tmpResult.pop()                 #法2：基于交换     def Permutation2(self, ss):         n = len(ss)         if n==0:             return []         result = []         ssList = list(ss)         ssList.sort()#避免后面的计算结果集重复         self.getPermutation2(ssList, result, 0, n-1)         #result.sort()         return result           def getPermutation2(self, ss, result, start, end):         if start>end:             result.append("".join(ss))             return                   ss = ss[:start]+sorted(ss[start:end+1])################排序是为了避免后面的计算结果集重复         for i in range(start, end+1):             if i>start and ss[i]==ss[i-1]:#遇到重复字母，不重复计算                 continue             ss[start], ss[i] = ss[i], ss[start]             self.getPermutation2(ss, result, start+1, end)             ss[start], ss[i] = ss[i], ss[start]             #法3：基于交换,更简单的写法     def Permutation(self, ss):         n = len(ss)         if n==0:             return []         result = []         ssList = list(ss)         ssList.sort()#避免后面的计算结果集重复         self.getPermutation(ssList, result, 0, n-1)         return result           def getPermutation(self, ss, result, start, end):         if start>end:             result.append("".join(ss))             return                   #ss = ss[:start]+sorted(ss[start:end+1])################排序是为了避免后面的计算结果集重复         for i in range(start, end+1):             if i>start and ss[i]==ss[i-1]:#遇到重复字母，不重复计算                 continue             ss[start], ss[i] = ss[i], ss[start]             self.getPermutation(ss[:], result, start+1, end)#####注意这里的ss[:]             #ss[start], ss[i] = ss[i], ss[start]

c++实现：

class Solution { public:     vector<string> Permutation1(string str) {         vector<string> result;         if(str.length()==0)             return result;         int n = str.length();         string tmpResult;         getPermutation1(str, result, tmpResult, n);         sort(result.begin(), result.end());         return result;     }           void getPermutation1(string str, vector<string> &result, string &tmpResult, int n){         if(tmpResult.length()==n){             result.push_back(tmpResult);             return;         }         set<char> tmpStrSet(str.begin(), str.end());         //sort(ss.begin(), ss.end());         for(auto ch: tmpStrSet){             //tmpResult += ch;             tmpResult.push_back(ch);             int idx = str.find(ch);             string str1 = str;             str1.erase(idx, 1);             getPermutation1(str1, result, tmpResult, n);             tmpResult.pop_back();         }     }                 //法3：基于交换     vector<string> Permutation(string str) {         vector<string> result;         if(str.length()==0)             return result;         int n = str.length();         sort(str.begin(), str.end());//排序有助于计算后面的结果集不重复         getPermutation(str, result, 0, n-1);         return result;     }                 void getPermutation(string str, vector<string> &result, int start, int end){         if(start>end){             result.push_back(str);             return;         }         for(int i=start; i<=end; i++){             if(i>start && str[i]==str[i-1])                 continue;             swap(str[start], str[i]);             getPermutation(str, result, start+1, end);         }     } };