《程序员面试100题 In Java》05.输出一个字符串的所有子串

题目:给定一个字符串,输出其所有子字符串,例如给定字符串abc,则输出 :a,b,c,d,ab,bc,cd,abc,bcd,abcd。


分析:今天看到csdn博客上面的一题,说是阿里巴巴电面的题目。初看到这道题的时候,就感觉很熟悉,在高中的时候,经常要算这种组合有多少个,当时我们计算的方法顺序是这样的:3+2+1   即

a,b,c,d,

ab,bc,cd,

abc,bcd,

abcd。

假如我们按照这种思路去写程序的话,你会发现很难写,因为当我们输出两个字符的子串时,他们在abcd中可能是不连续的,记住程序在处理连续问题要简单些,所以我们就要变化个思路,将其转为连续。也就是以如下顺序输出的。

 "a","ab","abc","abcd",          

"b","bc","bcd",

"c","cd",

"d"

看到这种形式很容易让我们想到递归的方法,第一次以a开头,第二次以b开头。。。确定开头后之后的操作是一样的。

有递归法就一般可以转为非递归。


解法一:递归法

void findAllSubstrings(const char *s){
    int x=0;
    while(*(s+x)){
        for(int y=0; y<=x; y++)
            cout<<*(s+y);
        cout<<‘\n‘;
        x++;
    }
    if(*(s+1))
        findAllSubstrings(s+1);
    else
        return;
}

解法二:非递归

void findAllSubstrings(String str,int length){
	for(int i = 0 ; i < length ; i++ ){
		for(int j = 1 ; j <= length - i ; j++ ){
			sub = str.substring(i, i+j);
			System.out.println(sub);
		}
	}
}


《程序员面试100题 In Java》05.输出一个字符串的所有子串,布布扣,bubuko.com

《程序员面试100题 In Java》05.输出一个字符串的所有子串

上一篇:C函数仿写 JAVA::String操作


下一篇:javascript中获取昨天、明天时间等