字符串全排列

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路

  1. 首先,我们固定第一个字符a,求后面两个字符bc的排列
  2. 当两个字符bc排列求好之后,我们把第一个字符a和后面的b交换,得到bac,接着我们固定第一个字符b,求后面两个字符ac的排列
  3. 现在是把c放在第一个位置的时候了,但是记住前面我们已经把原先的第一个字符a和后面的b做了交换,为了保证这次c仍是和原先处在第一个位置的a交换,我们在拿c和第一个字符交换之前,先要把b和a交换回来。在交换b和a之后,再拿c和处于第一位置的a进行交换,得到cba。我们再次固定第一个字符c,求后面两个字符b、a的排列
  4. 既然我们已经知道怎么求三个字符的排列,那么固定第一个字符之后求后面两个字符的排列,就是典型的递归思路了
Paste_Image.png
class Solution {
public:
    vector<string> result;
    vector<string> Permutation(string str) {
        if(str.length()==0)
            return result;
        
        PermulationImpl(str,0);
        sort(result.begin(),result.end());
        return result;
    }
    
    void PermulationImpl(string str, int begin){
        if(begin==str.length()){
            result.push_back(str);
            return;
        }
        
        for(int i=begin;str[i]!='\0';i++){
            if(i!=begin && str[begin]==str[i])
                continue;
            swap(str[begin],str[i]);
            PermulationImpl(str,begin+1);
            swap(str[begin],str[i]);
        }
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 一、题目 输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串abc。则打印出由字符a、b、c 所能排列...
    brzhang阅读 365评论 0 1
  • 今天学习了字符串全排列问题的递归与非递归实现,其中,递归实现是把递归放在循环中,到现在我也没看懂到底是个什么样的过...
    pw007992阅读 764评论 0 1
  • 经常会遇到字符串全排列的问题。例如:输入为{‘a’,’b’,’c’},则其全排列组合为abc,acb,bac,bc...
    帝Bug阅读 280评论 0 2
  • 声明: 本总结仅为个人学习总结,以防止遗忘而作,不得转载和商用。给定一个字符串,求一个字符串的全排列组合起点:字典...
    春天还没到阅读 903评论 0 0
  • 字符串的全排列 题目描述: 输入一个字符串,打印出该字符串中字符的所有排列。 例如输入字符串abc,则输出由字符a...
    MinoyJet阅读 11,298评论 4 11