字母组合问题

Problem

写一个函数,打印两个string的字母组合,但各个字母必须保留在源字符串的字母顺序.比如:

input:str1="AB" str2="C" output:
ABC ACB CAB

input:str1="AB" str2="BC" output: ABCD ACBD ACDB CABD CADB CDAB

Analysis

和普通的全排列不同(话说全排列一直没弄明白),这里的场景需要保留源字符串的字母顺序.昨天在兰亭集势的笔试上没做出来,今天花了时间考虑:

• 可以利用递归的思路
• 开辟一个足够长的全局数组.维护结果字符串的当前位置.当前字符只能来自str1或者str2.针对这两种情况分别进行递归.
• 当结果字符串的长度等于str1和str2的和时,输出字符串(递归返回)

Implementation

const int MAXLEN=26;
int myIndex=0;
char result[MAXLEN-1];
int len=0;
void CombineLetter(const char* index1,const char* index2)
{
    if(myIndex==len)
    {
        result[myIndex+1]='\0';
        printf("%s\n", result);
        return;
    }
    if(*index1!='\0')
    {
        result[myIndex]=*index1;
        myIndex++;
        index1++;
        CombineLetter(index1,index2);

        index1--;
        myIndex--;
    }

    if(*index2!='\0')
    {
        result[myIndex]=*index2;
        index2++;
        myIndex++;
        CombineLetter(index1,index2);
        index2--;
        myIndex--;
    }
}