面试题28：字符串全排列

字符串全排列是面试中常考的问题，一定要掌握

这题没写出来，思路就是把第一个字符和后面所有字符交换，然后递处理后面n-1个，最后需要在调用交换函数换回原始字符串

 1 #include<iostream>
 2 using namespace std;
 3 #include<assert.h>
 4 
 5 void Permutation(char* pStr, char* pBegin)
 6 {
 7     assert(pStr && pBegin);
 8 
 9     if(*pBegin == '')
10         printf("%s
",pStr);
11     else
12     {
13         for(char* pCh = pBegin; *pCh != ''; pCh++)
14         {
15             swap(*pBegin,*pCh);
16             Permutation(pStr, pBegin+1);
17             swap(*pBegin,*pCh);
18         }
19     }
20 }
21 
22 int main(void)
23 {
24     char str[] = "abc";
25     Permutation(str,str);
26     return 0;
27 }

http://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&rp=2&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking

牛客网上的输入可能有重复，需要做去重处理

class Solution {
public:
    vector<string> result;
    vector<string> Permutation(string str) { 
        if(str.empty())
            return result;
        Permutation(str,0);
        return result;
    }
    void Permutation(string str,int i)
    {
        if(i == str.length())
            result.push_back(str);
        else
        {
            for(int j = i;j < str.length();j++)
            {
                sort(str.begin() + i,str.end());    //先对str按字典排序
                if(i != j && str[i] == str[j])    //方式aa这种输出两次
                    continue;
                swap(str[i],str[j]);
                   Permutation(str,i+1);
                swap(str[i],str[j]);     
            }
        }
    }
};

更多字符串排列问题参考：http://blog.csdn.net/hackbuteer1/article/details/7462447

总结全排列递归问题：

if和递归调用控制一个总体循环，for控制剩余循环

fun(数组，起始遍历位置)
{
    if (终止条件)
        操作;
    else
    for (遍历数组)
    {
        swap();
        fun(); 递归调用
        swap();
    }
}

8皇后问题可参考全排列解法