字符串的排列

字符串的排列

http://www.nowcoder.com/questionTerminal/4f31423f126749ab9196c97c5117bcb9

题解:

考察点:深度优先搜索,回溯,剪枝

易错点:

字符串中的字母有重复,直接使用全排列生成的字符串会有重复,需要通过剪枝或者等手段去重。

方法一:回溯+去重

回溯法是一种深度优先搜索中常用的一种手段,基本思想是首先按选设定条件进行深度搜索,当探索到某一步时,发现原先搜索的路径并不满足,就退回上一步重新选择。在全排列问题中,首先设置一个指针,代表当前生成的字符串中的元素个数,设置一个数组表示每个位置是否被访问过,然后按照从前往后的顺寻,选择未被访问过的字母进入字符串,每次被选择的位置把标记为已访问,在进行深度优先搜索之后再将标记释放,进行回溯。注意,因为字母有重复,因此生成的全排列也会有重复,需要进行去重。

#include "bits/stdc++.h"
using namespace std;
string s;
int vis[10];
void dfs(set<string>&res,string ans,vector<int> num,int pos){
    if(pos==num.size()){
        res.insert(ans);
    }
    for(int i=0;i<num.size();i++){
        if(!vis[i]){
            vis[i]=1;
            ans.push_back(num[i]+'a');
            dfs(res,ans,num,pos+1);
            vis[i]=0;
            ans.pop_back();
        }
    }
}
int main()
{
    cin>>s;
    vector<int>num;
    for(int i=0;i<s.length();i++) num.push_back(s[i]-'a');
    set<string>res;
    string ans="";
    dfs(res,ans,num,0);
    int tmp=0;
    int len=res.size();
    for(auto s:res){
        ++tmp;
        if(tmp==1){
            cout<<"["<<s<<", ";
        }else if(tmp==len){
            cout<<s<<"]"<<endl;
        }else{
            cout<<s<<", ";
        }
    }
    return 0;
}

方法二:回溯+剪枝

可以对上述方法进行改进,由于有重复字母存在,可以考虑生成答案的过程中对重复字母进行剪枝。对于两个重复元素,在全排列中交换其位置不会生成新的排列,基于这个思想,首先会对字母进行排序,这样确保重复元素相邻。那么假设当前位置为,在枚举排列的时候,保证当前位置的字母和之前的一样,并且之前的字母没有被标记,则可以把这种情况剪枝掉。

#include "bits/stdc++.h"
using namespace std;
string s;
int vis[10];
void dfs(vector<string>&res,string ans,vector<int> num,int pos){
    if(pos==num.size()){
        res.push_back(ans);
    }
    for(int i=0;i<num.size();i++){
        if(!vis[i]){
            if(i>0&&num[i]==num[i-1]&&!vis[i-1]) continue;
            vis[i]=1;
            ans.push_back(num[i]+'a');
            dfs(res,ans,num,pos+1);
            vis[i]=0;
            ans.pop_back();
        }
    }
}
int main()
{
    cin>>s;
    vector<int>num;
    for(int i=0;i<s.length();i++) num.push_back(s[i]-'a');
    sort(num.begin(),num.end());
    vector<string>res;
    string ans="";
    dfs(res,ans,num,0);
    for(int i=0;i<res.size();i++){
        if(i==0){
            cout<<"["<<res[i]<<", ";
        }else if(i==res.size()-1){
            cout<<res[i]<<"]"<<endl;
        }else{
            cout<<res[i]<<", ";
        }
    }
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 18:35
简历上把1个月实习写成了3个月,会进行背调吗?
码农索隆:一个月有一个月的实习经历,三个月有三个月的实习经历
点赞 评论 收藏
分享
找个工作&nbsp;学历是要卡的&nbsp;要求是高的&nbsp;技能不足是真的&nbsp;实习经验是0的&nbsp;简历无处可写是事实的&nbsp;钱不好赚是真的&nbsp;想躺平又不敢躺&nbsp;也不甘心躺&nbsp;怕自己的灵感和才华被掩埋甚至从未被自己发现&nbsp;又质疑自己是否真正有才华
码农索隆:你现在啊,你心里都明白咋回事,但是你没办法改变现状,一想到未来,你又没有信心狠下心来在当下努力。 得走出这种状态,不能一直困在那里面,哪不行就去提升哪,你一动不动那指定改变不了未来,动起来,积少成多才能越来越好
点赞 评论 收藏
分享
06-07 19:59
门头沟学院 C++
补药卡我啊😭:都快15年前的了还在11新特性
你的简历改到第几版了
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务