It's not a secret anymore!*
The moose likes Java in General and the fly likes recursion problem Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "recursion problem" Watch "recursion problem" New topic
Author

recursion problem

Adam Frank
Greenhorn

Joined: Jan 22, 2009
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
Marshal

Joined: Mar 22, 2005
Posts: 41087
    
  43
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.


Ping & DNS - my free Android networking tools app
Adam Frank
Greenhorn

Joined: Jan 22, 2009
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

Joined: Aug 03, 2008
Posts: 9291
    
  17

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??


SCJP 6 | SCWCD 5 | Javaranch SCJP FAQ | SCWCD Links
Adam Frank
Greenhorn

Joined: Jan 22, 2009
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"
Adam Frank
Greenhorn

Joined: Jan 22, 2009
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

Joined: Oct 14, 2002
Posts: 8801
    
    5
intermediate


Spot false dilemmas now, ask me how!
(If you're not on the edge, you're taking up too much room.)
Martijn Verburg
author
Bartender

Joined: Jun 24, 2003
Posts: 3274
    
    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)


Cheers, Martijn - Blog,
Twitter, PCGen, Ikasan, My The Well-Grounded Java Developer book!,
My start-up.
Tony Docherty
Bartender

Joined: Aug 07, 2007
Posts: 2170
    
  47
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: recursion problem
 
Similar Threads
Garbage Collection of Strings
GC
question about gc
Checking whether a string is a substring of another string without using indexOf method
Uploading jpeg images to webserver