华为笔试题:递归打印输出子字符串

一、文章来由

一道面试题而已~~~

二、题目

从n个不同字符中任取m个字符组合
描述: 题目描述:

输入含有n个字符的字符串,字符串中没有重复字符,任取m个字符进行组合,按字符原位置顺序(从左至右)依次输出所有组合形式的字符串,每种组合间使用空格隔开。

例如:

1)输入字符串是"abc", m = 2, 则输出"ab ac bc"。

   【说明】输出"ac bc ab"和"ab bc ac"是不正确的,因为未按原字符位置顺序输出)。

2)如果输入有误(例如m=0 或 m>n), 则输出"ERROR"。 

运行时间限制: 1 Sec
内存限制: 128 MByte
输入: n个不重复字符的字符串

输出: 所有组合形式的字符串(每种组合间使用空格隔开)

样例输入: abc 2
样例输出: ab ac bc

三、代码

#include <iostream>
#include <string>
using namespace std;

char in[1024];
char out[1024];

void work(char *in,char *out,const int length,int cur,int start,const int m)
{
    if( cur>m )
        return;

    int i;
    for(i=start;i<length;i++)
    {
        out[cur] = in[i];
        out[cur+1] = '\0';

        (m == strlen(out))?
            cout<<out<<"\n":true;

        (i<length-1)?
            work(in, out, length, cur+1, i+1,m):true; //cur = 层数
    }
}

int main()
{
    int m;
    cin>>in;
    cin>>m;
//  char *in="abcde";
//  m=3;

    m>strlen(in)?
        (cout<<"ERROR"<<endl):true;

    work(in, out, strlen(in), 0, 0, m);

    return 0;
}

分析:

类似打印输出一个字符串的所有子串,然后递归,有剪枝,特别注意函数中的 cur 类似代表当前递归层数,比如abcdef,当前确定 ab,cur为2(第三层),ab | cdef,这样第三层有 cdef 四种可能,每一种可以再往下分支。

在网上找到一个不错的指针写法:

#include <iostream>
#include <string>

using namespace std;

//组合问题(从M个不同字符中任取N个字符的所有组合)
void combine(char *source,char *result,int n){

    //平凡情况
    if (1==n){
        while (*source)
        {
            printf("%s%c\n",result,*source++);
        }
    }

    else{
        int i,j;
        for (i=0;source[i]!='\0';i++); //当前字符串长度
        for (j=0;result[j]!='\0';j++);
        for (;i>=n;i--)
        {
            result[j]=*source++;
            result[j+1]='\0';
            combine(source,result,n-1);
        }
    }
}

int main(int argc, char* argv[])
{
    int const n=4;
    char *source="abcdef",result[n+1]={'\0'};
    if (n>0 && strlen(source)>0 && n<=strlen(source))
    {
        combine(source,result,n);
    }
    //getchar();
    return 0;
}

—END—


上一篇:Vue中回调函数内使用this无效


下一篇:自定义包和系统包重名,导致解释器找不到系统包:ModuleNotFoundError: No module named ‘http.client‘; ‘http‘ is not a package