剑指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.2.1: 第三位是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.2.1: 第三位是a,所以此时和前缀进行拼接构成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.2.1: 第三位是b,所以此时和前缀进行拼接构成cab.作为输出结果。
    综上所述，最终结果有六个{abc,acb,bac,bca,cba,cab}
    但是考虑到一个情况是如果有重复字符，比如两个a,
    那么按照上面的基于前缀的答案就变成了{aa,aa},而我们想要的答案是{aa},
    所以我们最后可以通过set来进行去重，并按字典序保存结果。

思路3

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

上面这个图也很经典，
第一列到第二列，是把索引为0的字符依次和每个字符交换。
接着在每个分支中，把索引为1的字符依次和它及后面的字符交换。
最后处理索引为2的字符，此时只剩它自己。
从而实现了字符的全排列。
为什么说这个方法可以避免重复元素呢。
以bb来举例。如果按照前缀进行排列且未经过set处理，必然结果是{bb,bb}。
基于交换的方法在每一层只尝试不同的字符。索引0先和自己交换，再递归处理索引1，得到bb。回到第一层后，准备交换索引0和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;
        sort(str.begin(),str.end());
        do{
            res.push_back(str);
        }while(next_permutation(str.begin(),str.end()));
        return res;
    }
};

无重复字符时，时间复杂度和结果空间复杂度均为O(n*n!)。这里n是字符串长度，一共有n!种排列，每种都要保存n个字符。

思路2代码

class Solution {
public:
    vector<string> res;
    vector<string> Permutation(string str) {
        //方法2： 基于前缀的排列生成。每次在排完前面的之后，对后面所有的元素进行全排列
        res.clear();
        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(nn!)的时间和空间；加上set去重排序，总时间复杂度的上界为O(nn!*log(n!))。

思路3代码

class Solution {
public:
    vector<string> res;
    vector<string> Permutation(string str) {
        
        //方法3: 基于交换的全排列生成，可以避免有重复元素
        res.clear();
        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;
    }
};

无重复字符时有n!种排列，结果空间为O(nn!)。生成过程中包含字符串复制和重复字符检查，时间上界为O(n^2n!)，最后的排序还需要O(n*n!*log(n!))的最坏时间。

参考资料

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