-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path38_StringPermutation.cpp
More file actions
124 lines (102 loc) · 2.5 KB
/
38_StringPermutation.cpp
File metadata and controls
124 lines (102 loc) · 2.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#if 0
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
void PermutationDFS(char* pStr, vector<bool> &avail, vector<char> &perm)
{
if(perm.size() == strlen(pStr))
{
for(auto i : perm)
cout<<i;
cout<<endl;
return;
}
for(int i = 0; i < strlen(pStr); i++)
{
if(avail[i])
{
avail[i] = false;
perm.push_back(pStr[i]);
PermutationDFS(pStr, avail, perm);
perm.pop_back();
avail[i] = true;
}
}
}
void Permutation(char* pStr)
{
if(pStr == nullptr)
return;
vector<char> perm;
vector<bool> avail(strlen(pStr), true);
PermutationDFS(pStr, avail, perm);
}
#endif
/*******************************************************************
Copyright(c) 2016, Harry He
All rights reserved.
Distributed under the BSD license.
(See accompanying file LICENSE.txt at
https://github.com/zhedahht/CodingInterviewChinese2/blob/master/LICENSE.txt)
*******************************************************************/
//==================================================================
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 作者：何海涛
//==================================================================
// 面试题38：字符串的排列
// 题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，
// 则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
#include <cstdio>
void Permutation(char* pStr, char* pBegin);
void Permutation(char* pStr)
{
if(pStr == nullptr)
return;
Permutation(pStr, pStr);
}
void Permutation(char* pStr, char* pBegin)
{
if(*pBegin == '\0')
{
printf("%s\n", pStr);
}
else
{
for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)
{
char temp = *pCh; //交换
*pCh = *pBegin;
*pBegin = temp;
Permutation(pStr, pBegin + 1);
temp = *pCh; //再交换回来
*pCh = *pBegin;
*pBegin = temp;
}
}
}
// ====================测试代码====================
void Test(char* pStr)
{
if(pStr == nullptr)
printf("Test for nullptr begins:\n");
else
printf("Test for %s begins:\n", pStr);
Permutation(pStr);
printf("\n");
}
int main(int argc, char* argv[])
{
Test(nullptr);
char string1[] = "";
Test(string1);
char string2[] = "a";
Test(string2);
char string3[] = "ab";
Test(string3);
char string4[] = "abc";
Test(string4);
char string5[] = "abbc"; // 未考虑字符重复的情况
Test(string5);
return 0;
}