Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# recursion problem

Greenhorn
Posts: 4
i am trying to write a recursion which finds the longest sequence of string2 containting only letters from string1. for example if string1="abc" and string2="wacdbgabcf" the answer will be 4 as "acdb" is the longest substring of s2 containg only letters from string1.
to answer this question with recursion i decided first to find the number of letters of string1 in string 2 so wrote the following code

i think that it doesn't work because substring takes the right part of the string and i am searching from the left side but i don't have any idea how to fix it.

1. can you help me solve the problem?
2. am i going in the right way to solve the original problem or should i use a different way?
thanks.

Ulf Dittmer
Rancher
Posts: 42968
73
I'd start by figuring out why the simple cases don't work, e.g.

"a" and "ab" --> 0

"a" and "ba" --> 2

when both should be 1.

Greenhorn
Posts: 4
Ulf Dittmer wrote:I'd start by figuring out why the simple cases don't work, e.g.

"a" and "ab" --> 0

"a" and "ba" --> 2

when both should be 1.

i see that it checks the last char in the first time the recursion is called and also in the second time.
i have to check the leftest char so i changed c to be c = s2.charAt(0) it works for the cases you wrote but not for "a" and "aaa"

Ankit Garg
Sheriff
Posts: 9543
33
Adam Frank wrote:for example if string1="abc" and string2="wacdbgabcf" the answer will be 4 as "acdb" is the longest substring of s2 containg only letters from string1.
to answer this question with recursion i decided first to find the number of letters of string1 in string 2

I didn't understand this. string1 contains only abc then why do you think that the answer should be abcd??

Greenhorn
Posts: 4
Ankit Garg wrote:
Adam Frank wrote:for example if string1="abc" and string2="wacdbgabcf" the answer will be 4 as "acdb" is the longest substring of s2 containg only letters from string1.
to answer this question with recursion i decided first to find the number of letters of string1 in string 2

I didn't understand this. string1 contains only abc then why do you think that the answer should be abcd??

sorry. my mistake. i had to write string1="abcd"

Greenhorn
Posts: 4
i see that the recursion checks every time the first char but the recursion stops after two cycles.
can you help me fix it?

Bert Bates
author
Sheriff
Posts: 8900
5
intermediate

Martijn Verburg
author
Bartender
Posts: 3275
5
I'm guessing that in your recursive calls that one of the 2 return statements below is being triggered.

So you'll want to check, which one of those is being called and then how is the if clause being triggered (hint print out s1.length and s1.indexOf(c) as you go)

Tony Docherty
Bartender
Posts: 3048
59
can you help me fix it?
I suggest you forget the coding side of the problem for the moment and write down a list of steps you need to complete to solve the problem. Then, once you have the algorithm sorted convert it to code. Trying write a straight to code solution for this sort of problem (and expecting to get it right first time) is beyond most people.