题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
示例一
输入
"ab"
返回值
["ab","ba"]
解题思路
解题思路参考字符串全排列(字典序法)
代码
class Solution { public: vector<string> Permutation(string str) { vector<string> strline; if (str.length() == 0) { return strline; } else if (str.length() == 1) { strline.push_back(str); return strline; } else { sort(str.begin(),str.end()); /***************************************************/ /*************C++中有相关函数,可直接调用,如下*********/ /*do /**{ /** strline.push_back(str); /**}while(next_permutation(str.begin(), str.end()));*/ /****************************************************/ strline.push_back(str); bool bIsFinish = false; int indexI,indexJ; while (!bIsFinish) { bool bIsFind = false; for (int i = str.length()-2; i >=0; i--) { if (str[i] < str[i+1]) { indexI = i; bIsFind = true; break; } } if (bIsFind) { for (int j = str.length() - 1; j > indexI; j--) { if (str[j] > str[indexI]) { indexJ = j; break; } } swap(str[indexI],str[indexJ]); reverse(str.begin()+indexI+1, str.end()); strline.push_back(str); } else { bIsFinish = true; } } } return strline; } };