题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路:感觉是动态规划题,假设选第一个元素时,对于abc有三种情况,选a选b或者选c,假定第一次选a,那么第二次选项就有bc两种,等选完第二个剩最后一个的时候,顺序就已经定下来了。按照这个思路就可以写,主要还是需要利用递归,边界条件就是只剩一个数字时,停止。
代码如下:(我这里递归到下一层是直接删除某个位上的元素,也可以直接交换位置,然后从下个位置开始选择)
class Solution {
public:
vector<string> Permutation(string str) {
vector<string>Data;
if(str.empty())
return Data;
string myS;
searchStr(Data,str,myS);
sort(Data.begin(), Data.end());//最后需要排序下
return Data;
}
void searchStr(vector<string>& Data,string str,string m)
{
int len = str.length();
if(len == 1)
{
m.push_back(str[0]);
Data.push_back(m);
return;
}
string middle;
bool once;
for(int i = 0 ;i<len; i++)
{
once =true;
for(int j = 0; j <middle.length();j++){ //这里是为了防止相同数字,那么就不用继续选择
if(middle[j] == str[i]){
once = false;
break;
}
}
middle.push_back(str[i]);
if(once)
{
m.push_back(str[i]);
string ss = str;
ss.erase(i,1);
searchStr(Data,ss,m);
m.pop_back();
}
}
}
};