剑指offer - 面试题28：字符串的排列（递归＋去重）

题目：输入一个字符串，打印出该字符串中字符的所有排列。
例如：输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
但是，还应当考虑字符串中是否有重复元素，如“112”的全排列只有“112、121、211”三种情况；

思路分析：
（1）把一个字符串看成由两部分组成：第一部分为它的第一个字符，第二部分是后面的所有字符。
（2）求整个字符串的排列时，可以看成两步：首先求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换。第二步固定第一个字符，求后面所有字符的排列。此时，我们仍把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。然后把第一个字符逐一和它后面的字符交换 ……（很典型的递归思路）

第一种去重的思路：
借助map，实现去重的效果，具体实现如下：

#include <iostream>
using namespace std;
#include <map>
void Permutation(char *pStr, char *pBegin)
{
if (*pBegin == '')
{
printf("%sn", pStr);
}
else
{
map<char, int> mp; // 1
for (char *pCH = pBegin; *pCH != ''; ++pCH)
{
if (mp[*pCH] == 0) // 2
{
mp[*pCH] = 1; // 3
char temp = *pCH;
*pCH = *pBegin;
*pBegin = temp;
Permutation(pStr, pBegin + 1);
temp = *pCH;
*pCH = *pBegin;
*pBegin = temp;
}
}
mp.clear(); // 4
}
}
void Permutation(char *pStr)
{
if (pStr == NULL)
return;
Permutation(pStr, pStr);
}
int main(int argc, const char * argv[]) {
char str[] = "aac";
Permutation(str);
return 0;
}

第二种去重的思路：
要避免重复，就要保证我们枚举某个位置的元素时，不能枚举重复。
即当我们枚举第 i 个位置的元素时，若要把后面第 j 个元素和 i 交换，则先要保证 [i … j-1] 范围内没有和位置 j 相同的元素。有两种方法（1）可以每次在需要交换时进行顺序查找；（2）用哈希表来查重；下面使用方法（1）。
具体实现如下：

#include <iostream>
using namespace std;
//在pStr数组中，[pBegin,pEnd)中是否有字符与下标为pEnd的字符相等

bool IsSwap(char *pStr, char *pBegin, char *pEnd)
{
for (char *p = pBegin; p < pEnd; p++)
if (*p == *pEnd)
return false;
return true;
}
void Swap(char *a, char *b)
{
char t = *a;
*a = *b;
*b = t;
}
void Permutation(char *pStr, char *pBegin)
{
if (*pBegin == '')
{
printf("%sn", pStr);
}
else
{
for (char *pCH = pBegin; *pCH != ''; ++pCH)
{
if (IsSwap(pStr, pBegin, pCH))
{
Swap(pCH, pBegin);
Permutation(pStr, pBegin + 1);
Swap(pCH, pBegin);
}
}
}
}
void Permutation(char *pStr)
{
if (pStr == NULL)
return;
Permutation(pStr, pStr);
}
int main(int argc, const char * argv[]) {
char str[] = "aac";
Permutation(str);
return 0;
}

最后

以上就是激动手机为你收集整理的剑指offer - 面试题28：字符串的排列（递归＋去重）的全部内容，希望文章能够帮你解决剑指offer - 面试题28：字符串的排列（递归＋去重）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。