题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
解题思路:
/*
1.求的所有可能在第一个位置上的字符,即依次遍历后面的元素,如果与第一个元素不一样的话
就与第一个元素交换,然后每次交换后都对后面的n-1个元素进行递归(即每次交换后假设第一个
元素是确定的,再将对后面的那些元素当成一个整体,重新进行和前面一样的操作)
*/
//这个题我感觉很难,但是代码确实简单
class Solution { public: vector<string> result; vector<string> Permutation(string str) { int len = str.length(); if(len==0) return result; permutations(str, 0, len); return result; } void permutations(string str, int index,int len) { if(index==len-1) //当索引指向字符串尾部时,将str压入数组 { result.push_back(str); } for(int i=index;i<len;i++) { if(index!=i && str[i]==str[index]) // 保证当输入多个重复字符时,不会重复计算 continue; swap(str[i], str[index]); permutations(str, index+1, len); } } };