【面试题028】字符串的排列

【面试题028】字符串的排列

题目：

输入一个字符串，打印出该字符串中字符的所有排列。例如

输入字符串abc，则打印出由字符a,b,c所能排列出来的所有的字符串abc,acb,bac,bca,cab和cba。

StringPermutation.cpp

 C++ Code 

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

#include <iostream>

using namespace std;

void Permutation(char *pStr, char *pBegin);

void Permutation(char *pStr)
{
    if (pStr == NULL)
    {
        return;
    }
    Permutation(pStr, pStr);
}

void Permutation(char *pStr, char *pBegin)
{
    if(*pBegin == '')
    {
        cout << pStr << endl;
    }
    else
    {
        for (char *pCh = pBegin; *pCh != ''; ++pCh)
        {
            char temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;

            Permutation(pStr, pBegin + 1);

            temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;
        }
    }
}

// ====================测试代码====================
void Test(char *pStr)
{
    if(pStr == NULL)
        cout << "Test for NULL begins:" << endl;
    else
        cout << "Test for %s begins:" << pStr << endl;

    Permutation(pStr);

    cout << endl;
}

int main()
{
    Test(NULL);

    char string1[] = "";
    Test(string1);

    char string2[] = "a";
    Test(string2);

    char string3[] = "ab";
    Test(string3);

    char string4[] = "abc";
    Test(string4);
    return 0;
}

运行结果：

 C++ Code 

1
2
3
4
5
6
7
8
9
10
11
12
13

Test(NULL);

char string1[] = "";
Test(string1);

char string2[] = "a";
Test(string2);

char string3[] = "ab";
Test(string3);

char string4[] = "abc";
Test(string4);