字符串的排列
字符串的排列
https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&rp=2&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=2
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
这题主要是生成字典顺序的全排列，把整个字符串想成一条路径，用dfs去搜索。
坑在去重。第一遍测试完忘记去重了，简单想了一种方法等字符排列完再从vector里面删除，但是没有技巧性。所以决定，在生成tempstr的过程中过滤重复。
class Solution {
public:
int len,k=0;
char cstr[10] = "";
vector<string> s;
string tempstr = "";
int visit[10] = {0};
void dfs(){
char tempc = '\0';//tempc为上一次的字符
if(k == len){
s.push_back(tempstr);
return ;
}
for(int i=0;i<len;i++){
if(!visit[i]&&tempc!=cstr[i]){//当前字符不能上次字符重复
tempc=cstr[i];
tempstr += cstr[i];
visit[i] = 1;
k++;
dfs();
k--;
visit[i] = 0;
tempstr.erase(k,1);
}
}
return ;
}
vector<string> Permutation(string str) {
len = str.size();
s.clear();
if(str.empty())
return s;
for(int i =0;i<len;i++){
cstr[i] = str[i];
}
sort(cstr,cstr+len);
dfs();
//sort(s.begin(),s.end());此时不用排序了 已经是字典序了。
return s;
}
}; 
腾讯公司福利 674人发布
