字符串的排列

问题描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述：输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
示例
输入："ab"
返回值：["ab","ba"]

方法一

思路分析

本题我们能想到的最直接的办法就是利用数学中的全排列，即对于一个字符串，首先确定第一个位置的字符，使用swap交换函数依次从当前位置的字符开始遍历寻找其余字符，从而得到第一个位置字符确定的字符串，而后其余位的字符也是用相同的办法，当确定到最后一个字符时，直接将最后一个字符插入到字符串中，递归结束，输出所有的排列。

图解

输入字符串“abc”,通过递归算法输出其全排列,通过第一次swap操作得到第一个位置上的确定字符，共三种情况，而后对剩余位的确定采用同样的办法。


C++核心代码 

class Solution {
public:
    vector<string> Permutation(string str) {
        if(str.empty())
            return {};
        set<string> tmp;
        perm(0, str, tmp);//从第一个位置开始递归
        return vector<string>({tmp.begin(), tmp.end()});
    }
    void perm(int pos, string s, set<string> &ret)
    {
        if (pos+1 == s.length())//运行到最后一个字符结束
        {
            ret.insert(s);
            return;
        }
        for (int i = pos; i < s.length(); ++i)
        {
            swap(s[pos], s[i]);//每次将当前位置的字符与后面的所有字符交换而形成不同的可能
            perm(pos+1, s, ret);//相同方法排列剩余的位
            swap(s[pos], s[i]);//将字符串归位
        }
            
    }
    
};

复杂度分析

  • 时间复杂度：字符串全排列的组合的时间为$O(n!)$，因此时间复杂度为$O(n!)$
  • 空间复杂度:  递归算法的空间复杂度为递归的深度*每次递归创建变量的个数，辅助数组tmp要放入的元素有$1+2+3+...+n=n(n-1)/2$，因此时间复杂度为$O(n^2)$

方法二

思路分析

  本题可以采用字典序的方法，字典序就是说给定两个字符串，逐个字符比较，那么先出现较小字符的那个串字典顺序小，例如abc>acb，那么本题可以先将给定的字符串按照字典序的顺序排序，形成最大字典序的字符串，例如给定字符串“abdc”，则其最大字典序的字符串为“abcd”，接着寻找下一个排列组合，为“abdc”，直到下一个排列组合为空，运行结束。接下来将介绍寻找下一个排列组合算法的思想步骤。
  • 首先将字符串按升序排序，找到字典序最大的字符串
  • 从字符串数组尾部开始从右往左寻找两个相邻元素(必须是相邻的)，左边元素为arr[i]，右边元素为arr[i+1]，并且arr[i]的字典序大于arr[i+1]
  • 之后再从尾端开始往前检验，找出第一个字典序小于arr[i]的元素arr[j]，交换两个元素
  • 将arr[i]之后的所有元素颠倒排序

实例分析

给定字符串“abc”,首先按升序方式找到最大的字符串，图中对调表示尾端开始往前检验，找出第一个字典序小于arr[i]的元素arr[j]，交换两个元素；重排表示arr[i]之后的所有元素颠倒排序；在此过程中将所有的排列输出


python核心代码 

# -*- coding:utf-8 -*-
class Solution:
    def Permutation(self, ss):
        # write code here
        n = len(ss)
        arr = list(sorted(ss))
        test = list(reversed(arr))
        ans = []
        # 生成下一个排列
        while arr != test:
            ans.append(''.join(arr))
            i = n - 2
            while i > 0 and arr[i] >= arr[i+1]:#从尾部开始往前检验，检验相邻位置的字典序大小
                i -= 1
            if i<0:return 
            j = n - 1
            while j > i-1 and arr[j] <= arr[i]:#找出第一个字典序小于arr[i]的元素arr[j]
                j -= 1
            m=arr[i]
            arr[i]=arr[j]
            arr[j]=m#交换两个元素元素
            arr = arr[:i+1] + sorted(arr[i+1:])#arr[i]之后的所有元素颠倒排序
        ans.append(''.join(test))#在此过程中将所有的排列输出
        return ans

复杂度分析

  • 时间复杂度：字符串全排列的时间复杂度为$O(n!)$，因此时间复杂度为$O(n!)$
  • 空间复杂度：借助于一个辅助数组存储字符串，空间复杂度为$O(n)$