剑指offer之字符串的全排列
【摘要】 1 问题
求字符串的全排列，比如字符串abc，它的全排列如下
abc, acb, bac, bca, cad, cba
2 思路
我们先固定第一个字符，这里的第一个字符肯定是这个字符串里面字符串的全子集（不包含重复），abc字符串，我们a和a交换，这里也就是固定a字符的，然...
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
文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。
原文链接：chenyu.blog.csdn.net/article/details/90745503
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）