算法进阶——字符串的排列

题目

---

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

数据范围：n<10

要求：空间复杂度 O(n!)，时间复杂度 O(n!)

输入描述：输入一个字符串,长度不超过10,字符只包括大小写字母。

示例1

输入：
"ab"
返回值：
["ab","ba"]
说明：
返回["ba","ab"]也是正确的

示例2

输入：
"aab"
返回值：
["aab","aba","baa"]

示例3

输入：
"abc"
返回值：
["abc","acb","bac","bca","cab","cba"]

示例4

输入：
""
返回值：
[""]

思路

---

使用递归的思路，每次先交换一个字符（可以是自己），然后将这个字符固定，之后递归的将后面的字符进行一次全排列，最后记得每次递归完需要回溯，也就是将交换的字符还原。

另外原字符串中可能存在重复的字符，如“aab”，经过递归后会有重复的，所以可以使用set来保存结果，以达到去重的效果。

递归三件套：

• 递归函数的功能：Permutation(int pos, string str), 表示固定字符串str的pos下标的字符str[pos]
• 递归终止条件：当pos+1 == str.length()的时候，终止。完成了一次全排列。
• 下一次递归：Permutation(pos+1, str), 很显然，下一次递归就是对字符串的下一个下标进行固定。

解答代码

---

#include <any>
#include <set>
#include <type_traits>
class Solution {
public:/*** @param str string字符串 * @return string字符串vector*/vector<string> Permutation(string str) {// write code herevector<string> ret{""};if (str.empty()) {return ret; }//用set去重set<string> no_repeat_ret;Permutation(0, str, no_repeat_ret);ret.assign(no_repeat_ret.begin(), no_repeat_ret.end());return ret;}void Permutation(int pos, string str, set<string>& no_repeat_ret) {if (pos+1 == str.length()) {// 递归终止条件：完成一次全排列no_repeat_ret.emplace(str);return;}for (int i = pos; i < str.length(); i++) {// 交换字符，固定一个字符swap(str[pos], str[i]);// 递归调用，对字符串的下一个下标进行固定Permutation(pos+1, str, no_repeat_ret);// 递归完需要回溯swap(str[pos], str[i]);}}
};