Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

recursion problem

 
Adam Frank
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Adam Frank
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 9528
33
Android Google Web Toolkit Hibernate IntelliJ IDE Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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??
 
Adam Frank
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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"
 
Adam Frank
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
intermediate
 
Martijn Verburg
author
Bartender
Posts: 3275
5
Eclipse IDE Java Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 2989
59
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic