企业信息网页模板,网站优化建设方案,商业网点建设开发中心网站,wordpress 博客标题题目 输入一个长度为 n 字符串#xff0c;打印出该字符串中字符的所有排列#xff0c;你可以以任意顺序返回这个字符串数组。 例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。 数据范围#xff1a;n10
要求#xff1a;空间复…题目 输入一个长度为 n 字符串打印出该字符串中字符的所有排列你可以以任意顺序返回这个字符串数组。 例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。 数据范围n10
要求空间复杂度 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]递归终止条件当pos1 str.length()的时候终止。完成了一次全排列。下一次递归Permutation(pos1, str), 很显然下一次递归就是对字符串的下一个下标进行固定。
解答代码 #include any
#include set
#include type_traits
class Solution {
public:/*** param str string字符串 * return string字符串vector*/vectorstring Permutation(string str) {// write code herevectorstring ret{};if (str.empty()) {return ret; }//用set去重setstring 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, setstring no_repeat_ret) {if (pos1 str.length()) {// 递归终止条件完成一次全排列no_repeat_ret.emplace(str);return;}for (int i pos; i str.length(); i) {// 交换字符固定一个字符swap(str[pos], str[i]);// 递归调用对字符串的下一个下标进行固定Permutation(pos1, str, no_repeat_ret);// 递归完需要回溯swap(str[pos], str[i]);}}
};
