【剑指Offer】（字符串）字符串的排列（回溯）

布满荆棘的人生 2022-03-12 10:21 206阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_fe6b651b66ae47d7acce78ffdd9a96c7_tpId_13_tqId_11180_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

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

##### 输入描述: #####

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

#### 回溯过程 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z1cWl1YWk_size_16_color_FFFFFF_t_70]

#### 解决方法 ####

class Solution { 
    public:
        vector<string> res;
        vector<string> Permutation(string str) { 
            //回溯。注：回溯是一种算法思想，可以用递归实现
            if(str.size()==0) return res;
            permute(str,0);
            sort(res.begin(),res.end());//按字典序输出
            return res;
        }
        void permute(string s,int begin){ //begin指向当前执行排列操作的字符串的第一个字符
            if(begin==s.size()) res.push_back(s);
            else{ 
                for(int i=begin;i<s.size();i++){ 
                    if(i!=begin && s[i]==s[begin]) continue;//去重
                    swap(s[begin],s[i]);
                    permute(s,begin+1);
                    swap(s[begin],s[i]);
                }
            }
        }
    };

[https_www.nowcoder.com_practice_fe6b651b66ae47d7acce78ffdd9a96c7_tpId_13_tqId_11180_tPage_1_rp_1_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Z1cWl1YWk_size_16_color_FFFFFF_t_70]: /images/20220312/f00503febca84db596c09ad0a6352c23.png