Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 5 of 5

Thread: Recursive Sentence Finder

  1. #1
    Junior Member
    Join Date
    Feb 2010
    Posts
    12
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Recursive Sentence Finder

    Hi all, I have a programming assignment that is described as follows:

    Use recursion to implement a method [B]boolean find(String t)[/B] that tests whether a string is contained in a sentence:
    [B]Sentence s = new Sentence("Mississippi!");
    boolean b = s.find("sip"); // Returns true[/B]

    Here is what I have done so far in my Sentence class:

    import java.util.ArrayList;
     
    public class Sentence
    {
    	public Sentence( String newWord )
    	{
    		word = newWord;
    	}
     
    	public boolean find( String find )
    	{	
    		if( !(word.substring( 0, find.length() ).equalsIgnoreCase(find) ) )
    		{
    			String shorterWord = word.substring( 1, word.length() );
    			Sentence shorterSentence = new Sentence( shorterWord );
    			shorterSentence.find(find);
    		}
    		else if( word.substring( 0, find.length() ).equalsIgnoreCase(find) )
    		{
    			result = true;
    		}
    		else if( word.length() == find.length() && !(word.substring( 0, find.length() ).equalsIgnoreCase(find) ) )
    		{
    			result = false;
    		}
     
    		return result;
    	}
     
    	private boolean result;
    	private String word;
    }

    What I have done is I have tested the substring from the start of the word to the length of word I am trying to find. If it does not match, then I take away the first letter to form a shorterWord, create a new setence and use the find() method on this word.

    I'm pretty new to recursive thinking and I thought I had done this correctly, but it does not yield the results I'm looking for. Can anyone help me with this? Thanks in advance.

    Here is my tester class:

    public class SentenceFinder
    {
    	public static void main(String[] args)
    	{
    		Sentence s = new Sentence( "Mississippi!" );
    		boolean b = s.find( "sip" );
    		System.out.println( b );
    	}
    }


  2. #2
    Member
    Join Date
    Feb 2010
    Location
    Auburn, AL
    Posts
    31
    Thanks
    0
    Thanked 8 Times in 8 Posts

    Default Re: Recursive Sentence Finder

    Change this line:
    shorterSentence.find(find);

    to this line:
    result = shorterSentence.find(find);

    There is also some tidying up you could do, but I think that the only problem with the code is the one already mentioned. Any other problems are syntax or style... unless I missed one...
    Let me know what you think of my website:
    http://www.auburn.edu/~carpept
    Comments or suggestions are appreciated!

  3. #3
    Junior Member
    Join Date
    Feb 2010
    Posts
    12
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Recursive Sentence Finder

    Thank you! It's been bothering me for a while now. Would you mind showing me how you would tidy up my code? I'd like to get into the right habits ahead of time so that I can continue practicing good programming.

  4. #4
    Member
    Join Date
    Feb 2010
    Location
    Auburn, AL
    Posts
    31
    Thanks
    0
    Thanked 8 Times in 8 Posts

    Default Re: Recursive Sentence Finder

    Sure. Of course, beauty is in the eye of the beholder, and maybe some other members can chime in, but...

    First, not that it matters, but I don't think this stipulation in the third elseif clause is necessary...
    && !(word.substring( 0, find.length() ).equalsIgnoreCase(find) )

    Why not? (when does the control reach that elseif clause?)

    Also, another problem that may actually be important - that is, affecting the correctness of the algorithm - that I didn't notice last time is that you should really have the recursive case handled AFTER the base cases have been checked. Why not?

    Take the sentence "blank" and look for the string "cat". Here's what the algorithm does...

    (blank, cat) = (lank, cat)
    (lank, cat) = (ank, cat)
    (ank, cat) = (nk, cat)
    (nk, cat) = (k, cat)
    (k, cat) = ( , cat)

    At that point, I don't really know what would happen. You should really make the code like this...

     
    if the sentence doesn't begin with word but len(sentence) = len(word)
       then result := false
    else if the sentence does begin with the word
       then result := true
    else
       then result := whatever the next recursive call gives you.

    Let's see... result should be defined locally within your method, and I like to put class members at the top rather than at the bottom of the class (bad habit from C++, maybe?)

    Other than that, really not too bad.
    Let me know what you think of my website:
    http://www.auburn.edu/~carpept
    Comments or suggestions are appreciated!

  5. The Following User Says Thank You to CT&SC For This Useful Post:

    raphytaffy (February 21st, 2010)

  6. #5
    Junior Member
    Join Date
    Feb 2010
    Posts
    12
    Thanks
    1
    Thanked 0 Times in 0 Posts

    Default Re: Recursive Sentence Finder

    Hi, thanks for the schooling. I did realize that the algorithm was a bit off and revised my code, I just didn't post the revised code:

    import java.util.ArrayList;
     
    public class Sentence
    {
    	public Sentence( String newWord )
    	{
    		word = newWord;
    	}
     
    	public boolean find( String find )
    	{	
    		if( word.length() == find.length() && !(word.substring( 0, find.length() ).equalsIgnoreCase(find) ) )
    		{
    			result = false;
    		}
    		else if( !(word.substring( 0, find.length() ).equalsIgnoreCase(find) ) )
    		{
    			String shorterWord = word.substring( 1, word.length() );
    			Sentence shorterSentence = new Sentence( shorterWord );
    			result = shorterSentence.find(find);
    		}
    		else if( word.substring( 0, find.length() ).equalsIgnoreCase(find) )
    		{
    			result = true;
    		} 
     
    		return result;
    	}
     
    	private boolean result;
    	private String word;
    }

    I still think that the third else if cause (the first one in the revised code above) is necessary. For example, if the word was "robot" and we were searching for "bot":

    (robot, bot) = (obot, bot)
    (obot, bot) = (bot, bot)

    If I took out that else if clause, word.length() would surely equal find.length() but it wouldn't check to see whether the words matched and would just denote to false. Adding !(word.substring(0, find.length() ).equalsIgnoreCase(find) ) ) allows it to check for equality (or non-equality in this case). That's the only way I could think of to get it to skip over this step if the words matched and go into the last else if clause (the one that sets result to true).

    Is my logic off here?

Similar Threads

  1. making a sentence proper
    By dvsumosize in forum Algorithms & Recursion
    Replies: 5
    Last Post: February 3rd, 2010, 10:01 AM
  2. recursive search of all local disks
    By ttsdinesh in forum Java Theory & Questions
    Replies: 4
    Last Post: September 27th, 2009, 08:23 AM
  3. reading a sentence
    By lotus in forum File I/O & Other I/O Streams
    Replies: 4
    Last Post: July 20th, 2009, 08:29 AM
  4. Recursive Solution to Knights tour
    By budder8818 in forum Algorithms & Recursion
    Replies: 0
    Last Post: February 4th, 2009, 02:31 PM