// 面试题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 pTemp = *pCh; *pCh = *pBegin; *pBegin = pTemp; Permutation(pStr, pBegin + 1); //求交换后半部分的排列 //求完后交换回来 pTemp = *pCh; *pCh = *pBegin; *pBegin = pTemp; } } }
// ====================测试代码==================== 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); return 0; }测试代码
分析:简洁。
class Solution { public: vector<string> Permutation(string str) { vector<string> result; if (str.empty()) return result; Permutation(str, result, 0); // 此时得到的result中排列并不是字典顺序,需要单独再排下序 sort(result.begin(),result.end()); return result; } void Permutation(string str, vector<string> &result, int begin) { if (begin == str.size()-1) { if(find(result.begin(), result.end(), str) == result.end()) { // 如果result中不存在str,才添加;避免aa和aa重复添加的情况 result.push_back(str); } } else { for (int i = begin; i < str.size(); ++i) { char pTemp = str[i]; str[i] = str[begin]; str[begin] = pTemp; Permutation(str, result, begin + 1); pTemp = str[i]; str[i] = str[begin]; str[begin] = pTemp; } } } };牛客网提交代码