字符的排列

剑指offer 字符串排列组合

Created At : 2019-12-26 23:12

Count:310 Views 👀 :

Comment:

题目描述
1. 解题思路

题目描述

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

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

解题思路

先不管是否有，递归实现，回溯筛选


class Solution {
public:
    set<string> permutationSet;// 全局变量，集合可以去除重复序列
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if (!(str.size()==0)){
            Permutation(str,0);// 递归求全排列
        }
        for (set<string>::iterator iter = permutationSet.begin();iter != permutationSet.end();iter++) {
            res.push_back(*iter);
        }
        return res;
    }
    
    void Permutation(string str,int n){
        if (n == str.size()) {        // 到达最后一个字符
            permutationSet.insert(str);// 存储该序列
        } else {
            Permutation(str,n+1);// 先递归到最后，之后再回溯
            for (int i = n+1;i < str.size();i++) {// 逐个替换
                if (str[i] != str[n]) { // 字符不等
                    // 交换字符
                    char tmp = str[i];
                    str[i] = str[n];
                    str[n] = tmp;
                    // 递归排列剩余字符
                    Permutation(str,n+1);
                    // 字符位置换回来
                    tmp = str[i];
                    str[i] = str[n];
                    str[n] = tmp;
                 }
            }
        }
    }
};

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com