职友集>程序员面试题 > 字符串的组合 --程序员面试题精选

字符串的组合 --程序员面试题精选

2015-11-17 06:30:01 阅读( 59 )

2343人 收藏本页

标签:程序员面试题

题目:输入一个字符串,输出该字符串中字符的所有组合。举个例子,如果输入abc,它的组合有a、b、c、ab、ac、bc、abc。

用递归的思路来求字符串的组合:

假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符,我们有两种选择:一是把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选取m-1个字符;而是不把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。

参考代码:

01.#include<iostream>
02.#include<vector>
03.using namespace std;
04.
05.void Combination(char *str, unsigned int number, vector<char> &result);
06.
07.void Combination(char *str)
08.{
09. if(!str)
10. return;
11.
12. unsigned int length = strlen(str);
13. vector<char> result;
14.
15. for(int i=1; i<=length; i++)
16. {//依次求 i 个字符组成的序列
17. Combination(str, i, result);
18. }
19.}
20.
21.void Combination(char *str, unsigned int number, vector<char> &result)
22.{
23. if(number == 0)
24. {// i 个字符的某个序列已选取完,输出之
25. vector<char>::iterator index = result.begin();
26. for(; index < result.end(); index++)
27. {
28. cout<<*index;
29. }
30. cout<<endl;
31. return;
32. }
33.
34. if(*str == '\0')
35. return;
36.
37. //把当前字符放入序列中,在剩下的串中选取number-1个字符的序列
38. result.push_back(*str);
39. Combination(str+1, number-1, result);
40. result.pop_back();
41.
42. //不把当前字符放入序列中,在剩下的串中选取number个字符的序列
43. Combination(str+1, number, result);
44.}
45.
46.
47.int main()
48.{
49. char *str = "abcd";
50. Combination(str);
51. system("pause");
52. return 0;
53.}

下一篇:程序员面试题精选--归并排序

上一篇:从头到尾输出字符串 --程序员面试题精选

亲~ 如果您有更好的答案 可在评论区发表您独到的见解。

您想查看更多的信息: 面试题