字符串的排列（dfs）1
需积分: 0 22 浏览量
2022-08-03
15:42:25
上传
评论
收藏 477KB PDF 举报
字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
class Solution {
public:
set<string> ss;
vector<string> res;
void dfs(string& str,string& tmp,vector<bool>& used)
{
if(tmp.size()==str.size())
{
ss.insert(tmp);//与原字符串相同字符数大小，认为此时 tmp 新串符合条件
存储在 set 后去重
return;
}
//若与原字符串字符数大小不相等，逐个构造
for(int i=0;i<str.size();i++)
{
if(used[i]) continue;
tmp+=str[i];//当前字符没有被使用过,进行构造
used[i]=true;//使用过后修改状态
//搜索，构造下一个字符
dfs(str,tmp,used);
//此时说明已经有一个字符串构造成功，构造下一个字符串之前需要将当前状
态恢复,并从后逐步替换字符从而构造新字符串
used[i]=false;
tmp.pop_back();
}
}
vector<string> permutation(string s) {
string tmp="";
vector<bool> used(s.size(),false);
dfs(s,tmp,used);
for(auto& ch:ss)
{
res.push_back(ch);//从去重 set 取出放在 res 中
评论0