剑指offer-字符串的排列
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
解题思路
此题目要求找出一个字符串的全排列,可以按照以下两步来递归的求解:
- 找到当前子字符串第一个字符的所有可能,可以通过将第一个字符依次与后面与其不相同的字符交换
- 固定第一个字符,找到后面所有字符的全排列
从字符串的第一个字符开始,按照上述步骤递归地向后交换并寻找全排列,当遍历到最后一个字符时,此时的字符串便是一种排列顺序,于是把当前字符串加入到vector容器中。
代码
1 class Solution { 2 public: 3 vector<string> v; 4 vector<string> Permutation(string str) { 5 if(str.size()) 6 Pmt(str,0); 7 return v; 8 } 9 void Pmt(string str,int f){ 10 if(f==str.size()-1) 11 v.push_back(str); 12 else{ 13 Pmt(str,f+1); 14 for(int i=f+1;i<str.size();i++){ 15 if(str[f]!=str[i]){ 16 swap(str[f],str[i]); 17 Pmt(str,f+1); 18 } 19 } 20 } 21 } 22 };
相关推荐
世事一场大梦 2020-11-17
wangzhaotongalex 2020-10-20
rechanel 2020-11-16
cakecc00 2020-11-06
cshanzhizi 2020-10-16
luofuIT成长记录 2020-09-22
周游列国之仕子 2020-09-21
PYTandFA 2020-09-15
taomengxing 2020-09-07
MaggieRose 2020-08-19
kevinweijc 2020-08-18
earthhouge 2020-08-18
yonggeno 2020-08-18
jyj00 2020-08-15
CXsilent 2020-08-12
amberom 2020-08-03
yiyilanmei 2020-08-03
纬纬 2020-07-31
zhuyonge 2020-07-26