面试题38:字符串的排序

题目

输入一个字符串，打印出该字符串中字符的所有排列。
例如，输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

解题思路

1. 求所有可能出现在第一个位置的字符，即把第一个字符和后面所有的字符交换
2. 固定第一个字符，求后面所有字符的排列(把后面的所有字符分成两部分:后面字符的第一个字符以及这个字符之后的所有字符，然后把第一个字符逐一和它后面的字符交换)。

代码

• 细节
  指针pstr指向整个字符串的第一个字符，指针pBegin指向当前我们执行排列操作的字符串的第一个字符。每一次递归的时候，从pBegin向后扫描每一个字符(指针pch指向的字符)。交换pBegin和pch指向的字符后，如果pbegin没有走到末尾，会一直交换到末尾然后输出此时的排序字符串，再返回。
  这个代码不好理解，我把每一步的输出放在这里。
  image.png
  第一个swap是求所有可能出现在第一个位置的字符。然后固定第一个字符，递归后面的字符并排序。第二个swap是把字符恢复原状(我个人理解，欢迎说出你的理解)。接着找第二个固定的字符，然后递归后面的字符并排序。

class Solution{
    public:
        void swap(char *a,char *b)
        {
            char temp = *a;
            *a        = *b;
            *b        = temp;
        }
        void percore(char *pstr,char *pbegin)
        {
            if(*pbegin == '\0')
            {
                cout <<pstr << endl;
            }
            else
            {
                for(char *pch=pbegin;*pch!='\0';pch++)
                {
                    //cout << "交换前:" << *pch << " " << *pbegin ;
                    swap(pch,pbegin);
                    //cout << " 交换后:" << *pch << " " << *pbegin << endl;;
                    percore(pstr,pbegin+1);
                    //cout << "递归后:" ; 
                    //cout << "交换前:" << *pch << " " << *pbegin ;
                    swap(pch,pbegin);
                    //cout << " 交换后:" << *pch << " " << *pbegin << endl;;
                }
            }
        }
        void Permutation(char str[])
        {
            percore(str,str);
        }
};

完整代码见Github