題目：輸入一個字符串，打印出該字符串中字符的所有排列。例如輸入字符串 abc ，則輸出由字符 a 、 b 、 c 所能排列出來的所有字符串 abc 、 acb 、 bac 、 bca 、 cab 和 cba 。

分析：這是一道很好的考查對遞歸理解的編程題，因此在過去一年中頻繁出現(xiàn)在各大公司的面試、筆試題中。

我們以三個字符abc為例來分析一下求字符串排列的過程。首先我們固定第一個字符a，求后面兩個字符bc的排列。當(dāng)兩個字符bc的排列求好之后，我們把第一個字符a和后面的b交換，得到bac，接著我們固定第一個字符b，求后面兩個字符ac的排列。現(xiàn)在是把c放到第一位置的時候了。記住前面我們已經(jīng)把原先的第一個字符a和后面的b做了交換，為了保證這次c仍然是和原先處在第一位置的a交換，我們在拿c和第一個字符交換之前，先要把b和a交換回來。在交換b和a之后，再拿c和處在第一位置的a進行交換，得到cba。我們再次固定第一個字符c，求后面兩個字符b、a的排列。

既然我們已經(jīng)知道怎么求三個字符的排列，那么固定第一個字符之后求后面兩個字符的排列，就是典型的遞歸思路了。

基于前面的分析，我們可以得到如下的參考代碼：

void Permutation(char* pStr, char* pBegin);/ // Get the permutation of a string, // for example, input string abc, its permutation is // abc acb bac bca cba cab / void Permutation(char* pStr) {Permutation(pStr, pStr); }/ // Print the permutation of a string, // Input: pStr - input string // pBegin - points to the begin char of string // which we want to permutate in this recursion / void Permutation(char* pStr, char* pBegin) {if(!pStr || !pBegin)return;// if pBegin points to the end of string,// this round of permutation is finished, // print the permuted stringif(*pBegin == '\0'){printf("%s\n", pStr);}// otherwise, permute stringelse{for(char* pCh = pBegin; *pCh != '\0'; ++ pCh){// swap pCh and pBeginchar temp = *pCh;*pCh = *pBegin;*pBegin = temp;Permutation(pStr, pBegin + 1);// restore pCh and pBegintemp = *pCh;*pCh = *pBegin;*pBegin = temp;}} }

擴展1：如果不是求字符的所有排列，而是求字符的所有組合，應(yīng)該怎么辦呢？當(dāng)輸入的字符串中含有相同的字符串時，相同的字符交換位置是不同的排列，但是同一個組合。舉個例子，如果輸入abc，它的組合有a、b、c、ab、ac、bc、abc。

擴展2：輸入一個含有8個數(shù)字的數(shù)組，判斷有沒有可能把這8個數(shù)字分別放到正方體的8個頂點上，使得正方體上三組相對的面上的4個頂點的和相等。

本文已經(jīng)收錄到《劍指Offer——名企面試官精講典型編程題》一書中，有改動，書中的分析講解更加詳細(xì)。歡迎關(guān)注。

本題已被九度Online Judge系統(tǒng)收錄，歡迎讀者移步到http://ac.jobdu.com/hhtproblems.php在線測試自己的代碼。

博主何海濤對本博客文章享有版權(quán)。網(wǎng)絡(luò)轉(zhuǎn)載請注明出處http://zhedahht.blog.163.com/。整理出版物請和作者聯(lián)系。對解題思路有任何建議，歡迎在評論中告知，或者加我微博http://weibo.com/zhedahht或者http://t.163.com/zhedahht與我討論。謝謝。

總結(jié)

以上是生活随笔為你收集整理的程序员面试题精选100题(28)-字符串的排列[算法]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。