程序員面試題精選100題(59)-字符串的組合[算法]

時間:2019-09-22 編輯:范文亭
題目:輸入一個字符串,輸出該字符串中字符的所有組合。舉個例子,如果輸入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<char> result;
    for(int i = 1; i <= length; ++ i)
    {
        Combination(string, i, result);
    }
}
 
void Combination(char* string, int number, vector<char>& result)
{
    if(number == 0)
    {
        vector<char>::iterator iter = result.begin();
        for(; iter < result.end(); ++ iter)
            printf("%c", *iter);
        printf("\n");
 
        return;
    }
 
    if(*string == '\0')
        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來存放選擇放進組合里的字符。
本文已影響
相關文章
大亨pk10计划苹果版