- 相关推荐
程序员面试题精选100题-字符串的组合[算法]
题目:输入一个字符串,输出该字符串中字符的所有组合。举个例子,如果输入abc,它的组合有a、b、c、ab、ac、bc、abc。
分析:在本系列博客的第28题《字符串的排列》中,我们详细讨论了如何用递归的思路求字符串的排列。同样,本题也可以用递归的思路来求字符串的组合。
假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符,我们有两种选择:一是把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选取m-1个字符;而是不把这个字符放到组合中去,接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码:
void Combination(char* string)
{
if(string == NULL)
return;
int length = strlen(string);
vector
for(int i = 1; i <= length; ++ i)
{
Combination(string, i, result);
}
}
void Combination(char* string, int number, vector
{
if(number == 0)
{
vector
for(; iter < result.end(); ++ iter)
printf("%c", *iter);
printf(" ");
return;
}
if(*string == )
return;
result.push_back(*string);
Combination(string + 1, number - 1, result);
result.pop_back();
Combination(string + 1, number, result);
}
由于组合可以是1个字符的组合,2个字符的字符……一直到n个字符的组合,因此在函数void Combination(char* string),我们需要一个for循环。另外,我们一个vector来存放选择放进组合里的字符。
[程序员面试题精选100题-字符串的组合[算法]]相关文章:
【程序员面试题100题-字符串的组合[算法]】相关文章:
程序员精选面试题100题07-13
程序员面试题精选100题(63)-数组中三个只出现一次的数字[算法]07-13
另一道递归算法题(2009年企业面试题)07-13
JAVA算法面试题:哪位高人会做?07-13
淘宝面试题求解--数据挖掘-算法07-13
2014年MBA面试题目大纲100题07-11
程序员面试题精选07-12
面试题原题归纳07-13