字符串的排列
题目描述:
输入一个字符串,按字典序打印出该字符串中字符的所有排列。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
输出描述:
输出为输入字符的全排列
示例:
输入:
abc
输出:
abc
acb
bac
bca
cab
cba
思路点拨:
- 将输入的字符串看作一个字符集合,如字符集{a,b,c}。
- 每次从字符集中取出一个字符到用于保存结果的数组
result
中。 - 用一个
bool
类型的数组flag
保存字符集中字符的状态,true
表示字符集中对应下标的字符已被提取,false
则表示未被提取。 - 当
flag
数组全为true
,表示一次字符排列已完成,保存result
中的字符集。 - 进行回溯,就是还原现场,删除
result
数组相应元素,并将flag
中相应字符状态置为false
,再递归算出下一种情况。 - 重复以上步骤n次,其中n为字符串长度。
根据以上分析,可以采用dfs进行深搜。代码如下:
void PermutationHelper(string str, vector<string> &result);
vector<string> Permutation(string str) {
vector<string> result; //用于保存全排列结果
if (str.empty())
return result;
PermutationHelper(str, result);
return result;
}
void PermutationHelper(string str, vector<string> &result){
static string temp; //用于保存一次排列的字符串
bool temp_tag = true; //一次排列是否完成
static bool flag[10] = {false}; //标记数组
for (size_t i = 0; i < str.size(); i++) {
/*该字符未被提取*/
if (!flag[i]) {
/*每次从字符集中提取出一个未被提取的字符到temp中*/
temp.push_back(str[i]);
flag[i] = true;
/*递归提取下一个字符*/
PermutationHelper(str, result);
/*回朔,恢复该字符的状态,并将其从temp中删除*/
flag[i] = false;
temp.erase(temp.size() - 1);
}
}
/*判断字符串中字符是否一全部提取*/
for (int i = 0; i < str.size(); i++) {
if (!flag[i]){
temp_tag = false;
break;
}
}
/*一次排序已完成,保存结果到result中*/
if (temp_tag) {
result.emplace_back(temp);
}
}
以上代码在输入字符串全部字符唯一时能正确运行,而一旦字符串中出现重复字符,输出结果就与预期不同。
比如,输入字符串为aab
,期望的结果为{aabyaba,baa},而使用上述代码的输出为{aab,aba,aab,aba,baa,baa},重复的排列被一起保存到输出了。出现以上情况是由于未考虑重复字符的情况,现对字符串中有重复字符进行考虑。
- 当字符集中存在相同的字符时,在该位置只需提取一次该字符,因为再次提取相同的字符,后续排列在第一次提取就已经出现了。比如
aab
在第一次,只提取一次a
,则结果就不会出现两个aab
和aba
的情况; - 当提取出一个字符(该字符在字符集中有相同的字符),需要记录当前字符集中该字符是否唯一,对于不唯一时,也只提取一次即可。同样,对于
aaab
,当第一个为a
,提取第二个时,由于字符集中还有两个a
,也只需提取一次,则结果中aaab
就只会出现一次。
由上述分析,需要记录字符集中相同字符的个数,由字符-个数的key-value关系,采用map来记录字符集中出现的字符以及相应的个数。
最后代码如下:
void PermutationHelper(string str, map<char, int> count, vector<string> &result);
vector<string> Permutation(string str) {
vector<string> result; //用于保存结果。
map<char, int> count; //保存字符集中出现字符的个数。
if (str.empty())
return result;
/*初始化count,将字符集中出现的字符以及次数记录*/
for (auto item : str)
++count[item];
PermutationHelper(str, count, result);
return result;
}
void PermutationHelper(string str, map<char, int> count, vector<string> &result){
static string temp; //用于保存一次排列的字符串
bool temp_tag = true; //一次排列是否完成
static bool flag[10] = {false}; //标记数组
int num = 0; //字符集剩余字符中某个字符的相同个数
for (size_t i = 0; i < str.size(); i++) {
if (flag[i])
continue;
/*由于输入字符串是按字典排序,相同的字符一定排列在一起。
*因此,只需改变i的值,取相同字符中最后一个即可。
*/
if (--count[str[i]] > 0)
continue;
/*记录该字符*/
temp.push_back(str[i]);
flag[i] = true;
/*剩余字符集中该字符的个数*/
for (size_t j = 0; j < str.size(); j++)
if (str[j] == str[i] && !flag[j])
num++;
count[str[i]] = num;
num = 0;
/*递归提取下一个字符*/
PermutationHelper(str, count, result);
/*回朔,恢复现场
*恢复该字符的状态,并将其从temp中删除
*字符集中该字符个数加一
*/
flag[i] = false;
++count[str[i]];
temp.erase(temp.size() - 1);
}
/*判断字符串中字符是否一全部提取*/
for (int i = 0; i < str.size(); i++) {
if (!flag[i]){
temp_tag = false;
break;
}
}
/*一次排序已完成,保存结果到result中*/
if (temp_tag) {
result.emplace_back(temp);
}
}