字符串的排列、组合《剑指offer》刷题

递归方法
1、全排列

//面试题28：字符串的排列 /* 从集合依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如此递归处理；n个数的全排列，一共有n！种情况. （n个位置，第一个位置有n种，当第一个位置固定下来之后，第二个位置有n-1种情况...）全排列的过程：选择第一个字符获得第一个字符固定下来之后的所有的全排列选择第二个字符获得第一+ 二个字符固定下来之后的所有的全排列从这个过程可见，这是一个递归的过程。 */ #include using namespace std; void Swap(char* c1, char* c2){ char temp = *c1; *c1 = *c2; *c2 = temp; } void Permutation(char* str, char* begin){ if (*begin == '\0'){ cout << str << endl; } else{ for (char* ch = begin; *ch != '\0'; ch++){ Swap(ch, begin); Permutation(str, begin + 1); swap(ch, begin); } } }void Permutation(char* str){ if (str == NULL){ return; } Permutation(str, str); }

测试

char str[] = "abc"; Permutation(str);

2、组合

//面试题扩展：字符串的组合 //递归 #include #include using namespace std; void Combination(char* str, int i, string& result); void Combination(char* str){ if (str == NULL){ return; }int length = strlen(str); string result; for (int i = 1; i <= length; i++){ Combination(str, i, result); } }void Combination(char* str, int number, string& result){ if (number == 0){ cout << result << endl; return; } else if (*str == '\0'){ return; } else{ result.push_back(*str); Combination(str + 1, number - 1, result); result.pop_back(); Combination(str + 1, number, result); } }

测试

char str[] = "abc"; Combination(str);

【字符串的排列、组合】3、基于位图的字符串的组合

//基于位图 /* 假设原有元素n个，最终的组合结果有2^n - 1. 可以使用2^n - 1个位，1表示取该元素，0表示不取。所以a表示001,取ab是011。 001,010,011,100,101,110,111。对应输出组合结果为：a,b,ab,c,ac,bc,abc。 */ void Combination_bit(char* str){ int length = strlen(str); if (length <= 0){ return; } else{ int n = 1 << length; //2^length for (int i = 0; i < n; i++){ string result; for (int j = 0; j < length; j++){ if ((i&(1 << j))!=0){ result.push_back(str[j]); } } cout << result << endl; } } }