字符串的排列(medium)"/>
[回溯]面试题38. 字符串的排列(medium)
题目:
题解:
- 回溯的基本框架,其中索引
index
用来表示需要进行排列的次数
,直到index==n表示我们已经生成一个排列了。
代码如下:
class Solution {
public:vector<bool> visit;vector<string> permutation(string s) {if(s.empty())return {};set<string> res;visit.resize(s.size(),false);string str;backtrack(s,res,str,0,(int)s.size());return vector<string> (res.begin(),res.end());}//回溯法基本框架:index用来表示使用字符使用的次数,直到使用了n个字符,表示我们已经生成一个排列了//visit用来标记字符是否已经使用,没有使用的字符可以使用void backtrack(string& s,set<string>& res,string& str,int index,int n){if(index>=n)res.insert(str);for(int i=0;i<n;++i){if(!visit[i]){//choose过程:将i号字符加入排列visit[i]=true;str.push_back(s[i]);//进行下一次回溯:index表示回溯的次数,index+1表示进行下一次回溯backtrack(s,res,str,index+1,n);//unchoose过程:将i号字符移除排列str.pop_back();visit[i]=false;}}}
};
更多推荐
[回溯]面试题38. 字符串的排列(medium)
发布评论