剑指offer之字符串的全排列
1 问题
求字符串的全排列,比如字符串abc,它的全排列如下
abc, acb, bac, bca, cad, cba
2 思路
我们先固定第一个字符,这里的第一个字符肯定是这个字符串里面字符串的全子集(不包含重复),abc字符串,我们a和a交换,这里也就是固定a字符的,然后我们只需要求出后面bc字符的全排列,这个时候我们可以用递归,我们依然b和b进行交换,c和c进行交换,到了末尾我们递归就结束,记得return.我们可以得出bc全排列的一种既bc,然后我们b和c需要交换位置,变成了cb,然后我们b和b进行了一次交换,然后我们可以得到bc全排列的一种既cb,所以固定a字符,我们可以得到全排列字符串abc acb,所以依次类推,我们可以固定b字符和c字符求出所以字符串的全排列
3 代码实现
c++版本
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class Permutation{
private:
void permutation(string str, int begin);
public:
vector<string> permutation(string str);
vector<string> result;
};
vector<string> Permutation::permutation(string str)
{
if (str.length() == 0)
{
return result;
}
permutation(str, 0);
sort(result.begin(), result.end());
return result;
}
void Permutation::permutation(string str, int begin)
{
if (begin == str.length())
{
result.push_back(str);
return;
}
for (int i = begin; i < str.length(); ++i)
{
if (i != begin && str[i] == str[begin])
continue;
//这里开始交换第一个元素和后面的元素,也就是起到固定的作用
swap(str[begin], str[i]);
//递归后面的子字符串
permutation(str, begin + 1);
//交换了要记得还原
swap(str[i], str[begin]);
}
}
int main()
{
Permutation h;
h.permutation("abc");
vector<string> result = h.result;
for(int i = 0; i < result.size(); ++i)
{
std::cout << result[i] << std::endl;
}
return 0;
}
c版本
#include <stdio.h>
void permutation(char *str);
void permutation_core(char *str, char *begin);
void permutation(char *str)
{
if (str == NULL)
{
printf("str is NULL\n");
return;
}
permutation_core(str, str);
}
void permutation_core(char *str, char *begin)
{
if (*begin == '\0')
{
printf("%s\n", str);
}
else
{
for (char *ch = begin; *ch != '\0'; ++ch)
{
char temp = *ch;
*ch = *begin;
*begin = temp;
permutation_core(str, begin + 1);
temp = *ch;
*ch = *begin;
*begin = temp;
}
}
}
int main()
{
//这里不能用char *str = "adc",因为我们需要交换字符串里面的字符,需要操作栈内存
char str[] = "abc";
permutation(str);
return 0;
}
这样写,如果有重复的字符就有问题,比如ada,我们优化如下,去掉重
#include <stdio.h>
#include <string.h>
void permutation(char *str);
void swap(char *str, int start, int end);
void permutation_core(char *str, int begin, int end);
void permutation(char *str)
{
if (str == NULL)
{
printf("str is NULL\n");
return;
}
int len = strlen(str);
printf("len is %d\n", len);
permutation_core(str, 0, len);
}
void permutation_core(char *str, int begin, int end)
{
if (begin == end)
{
printf("%s\n", str);
}
else
{
for (int i = begin; i < end; ++i)
{
if (i != begin && str[i] == str[begin])
continue;
swap(str, i, begin);
permutation_core(str, begin + 1, end);
swap(str, i, begin);
}
}
}
void swap(char str[], int start, int end)
{
char ch = str[start];
str[start] = str[end];
str[end] = ch;
}
int main()
{
//这里不能用char *str = "adc",因为我们需要交换字符串里面的字符,需要操作栈内存
char str[] = "abc";
permutation(str);
return 0;
}
4 运行结果
c++版本运行结果
abc
acb
bac
bca
cab
cba
c版本运行结果
abc
acb
bac
bca
cba
cab
赞 (0)