剑指offer-字符串的排列

本文为剑指 offer 系列第二十八篇。
主要知识点为字符串，给定n个字符，给出所有的可能的排列，非常经典。

题目描述

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

解题思路

思路1

可以直接使用stl中的next_permutation操作来依次的获得下一个排序的结果。

思路2

基于前缀的排列生成。每次在排完前面的之后，对后面所有的元素进行全排列。
以题目中的a,b,c为例进行说明。第一位有三种情况，

情况1:第一位是a,将a作为前缀，那么后面需要对b和c进行全排列
1. 情况1.1: 第二位是b,则此时就构成了ab，将ab作为前缀，然后对c进行全排列
  1. 情况1.1.1: 第三位是c,所以此时和前缀拼接构成abc.作为输出结果。
2. 情况1.2: 第二位是c,则此时就构成了ac, 将ac作为前缀，然后对b进行全排列
  1. 情况1.1.2: 第三位是b,所以此时和前缀拼接构成acb.作为输出结果。
情况2:第一位是b,将b作为前缀，那么后面需要对a和c进行全排列
1. 情况2.1: 第二位是a,则此时就构成了ba，将ba作为前缀，然后对c进行全排列
  1. 情况2.1.1: 第三位是c,所以此时和前缀进行拼接构成bac.作为输出结果。
2. 情况2.2: 第二位是c,则此时就构成了bc,将bc作为前缀，然后对a进行全排列
  1. 情况2.1.2: 第三位是b,所以此时和前缀进行拼接构成bca.作为输出结果。
情况3:第一位是c,将c作为前缀，那么后面需要对a和b进行全排列
1. 情况3.1: 第二位是b,则此时就构成了cb，将cb作为前缀，然后对a进行全排列
  1. 情况3.1.1: 第三位是a,所以此时和前缀进行拼接构成cba.作为输出结果。
2. 情况3.2: 第二位是a,则此时就构成了ca, 此时将ca作为前缀，然后对b进行全排列
  1. 情况3.1.2: 第三位是b,所以此时和前缀进行拼接构成cab.作为输出结果。
    综上所述，最终结果有六个{abc,acb,bac,bca,cba,cab}
    但是考虑到一个情况是如果有重复字符，比如两个a,
    那么按照上面的基于前缀的答案就变成了{aa,aa},而我们想要的答案是{aa},
    所以我们最后可以通过set来进行去重。

思路3

基于交换的全排列生成，可以避免有重复元素.

上面这个图也很经典，
第一列到第二列的变化是abc中的索引为0的字符和字符串的每个字符进行替换之后的样子。
第二列到第三列的变化是在第一列的基础上索引为1的字符和它以及它之后每个字符替换之后的样子。
第三列是在第二列的基础上索引为2的字符和它以及它之后每个字符进行替换之后的样子。
从而实现了字符的全排列。
为什么说这个方法可以避免重复元素呢。
以bb来举例。如果按照前缀进行排列且未经过set处理，必然结果是{bb,bb}。
而基于交换的方法的话，从0号索引开始和与前面字符不重复的每一位进行替换。所以索引0和索引0替换，得到{b,b},0和1进行替换的时候，发现之前已经存在b了，所以就不再替换。1和1替换的时候，发现之前也存在b了，所以也不再进行替换，所以最后结果仅仅只有{bb}，从而避免了重复。

解题代码

思路1代码

class Solution {
public:
    vector<string> Permutation(string str) {
        // 方法1： 直接使用stl中的next_permutation方法
        vector<string> res;
        if(str.size() == 0) return res;
        do{
            res.push_back(str);
        }while(next_permutation(str.begin(),str.end()));
        return res;
    }
};

时间复杂度为O(n),空间复杂度为O(n)

思路2代码

class Solution {
public:
    vector<string> res;
    vector<string> Permutation(string str) {
        //方法2： 基于前缀的排列生成。每次在排完前面的之后，对后面所有的元素进行全排列
        if(str.size() == 0) return res;
        helper2("",str);
        //去除重复元素 如 aa 前面的res会生成 aa 和 aa， 而我们的结果只要返回{aa}即可
        set<string> s(res.begin(),res.end());
        res = vector<string>(s.begin(),s.end());
        return res;
    }
    // 方法2的辅助函数。
    void helper2(string prefix, string str){
        if(str.size() == 0){
            res.push_back(prefix);
        }else{
            for(int i = 0;i < str.size(); i++){
                helper2(prefix+str[i],str.substr(0,i)+str.substr(i+1,str.size()));
            }
        }
    }
};

时间复杂度为O(n),空间复杂度为O(n)

思路3代码

class Solution {
public:
    vector<string> res;
    vector<string> Permutation(string str) {
        
        //方法3: 基于交换的全排列生成，可以避免有重复元素
        if(str.size() == 0) return res;
        helper3(str,0);
        sort(res.begin(),res.end());
        return res;
        
    }

    // 方法3的辅助函数
    void helper3(string str,int begin){
        if(begin == str.size()){
            res.push_back(str);
        }
        for(int i = begin; i< str.size(); i++){
           if(!HasDuplicate(str,begin,i)){
                swap(str[begin],str[i]);
                helper3(str,begin+1);
                swap(str[begin],str[i]);
            }
        }
        
    }
    bool HasDuplicate(string str,int begin,int end){
        for(int i = begin;i < end; i++){
            if(str[i] == str[end]) return true;
        }
        return false;
    }
};

时间复杂度为O(n),空间复杂度为O(n)

参考资料

1.剑指Offer–028-字符串的排列
以上，本题结束！