首页 > 文章 > 字符串的排列

字符串的排列

【问题】输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

【思路】如上图所示,树状图的第一层其实质就是下一个递归子问题入口str的值,也就是0与j(0,1,2…str.length())

交换后str的值,并且每次进入递归函数时,在i  之前字母将会被固定,其后面的数进行全排列(交换元素的位置)。然后一直递归下去,从而得到最后的全排列!一般我们写递归函数如果需要动态保存数据,如vector res, 我们可以把它当作一个参数,并使用引用传递的形式来修改res这个变量!

递归的结束条件为,索引i等于了str.length()时,递归结束!

class Solution {
public:
    void process(vector<string>& res, string str, int i){
        if(i == str.length()){
            res.push_back(str);
        }
        set<char> ss;
        for(int j = i;j < str.length(); j++){
            if(ss.find(str[j]) == ss.end()){
                ss.insert(str[j]);
                swap(str[i], str[j]);
                process(res, str, i+1);
            }
        }
    }

    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.length() == 0) return res;

        process(res, str, 0);
        return res;
    }
};

 

时间:2019-08-14 09:03:01阅读(15)
联系我们 - 留言反馈
© 2017 版权所有 鲁ICP备17052893号