• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

recursion problem

 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Rancher
Posts: 43081
77
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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"
 
Sheriff
Posts: 9707
43
Android Google Web Toolkit Hibernate IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
author
Posts: 9050
21
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
intermediate
 
author
Posts: 3285
13
Mac OS X Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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)
 
Bartender
Posts: 3323
86
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
reply
    Bookmark Topic Watch Topic
  • New Topic