Results 1 to 18 of 18
  1. #1
    kathyla18 is offline Member
    Join Date
    Feb 2009
    Posts
    16
    Rep Power
    0

    Default Reverse a string not using the substring method

    hi , i need to implement a method that reverses a string but i can only use the method length, concant and charAt. I know how to do it with for loops or with the substring method , but im supposed to do it with recursion and im not allow to use the substring method.
    Any help will be appreciated.

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    First thoughts:
    A) what will the method return?
    B) what will be the parameter passed to the method?

    Edit: I don't know if this is the simplest way to do it, but here is a method signature that worked for me:
    Java Code:
    public static String reverseString(String input, String output, int index) { //...
    Last edited by Fubarable; 04-07-2009 at 12:21 AM.

  3. #3
    kathyla18 is offline Member
    Join Date
    Feb 2009
    Posts
    16
    Rep Power
    0

    Default

    i have to use the method
    public String reverse(String string) and i can use helper methods

  4. #4
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    6

    Default

    just use fubarable's method (or some variation of it) as a helper.

    Java Code:
    public String reverse(String string) {
       String retval = "";
       return reverseString(string, retval, 0);
    }
    or something like that.

  5. #5
    rdtindsm is offline Member
    Join Date
    Feb 2009
    Posts
    92
    Rep Power
    0

    Default

    conceptually:
    string reverse(string){
    if string contains 1 character
    return string
    else
    return cancatonate(reverse(restof string), first element in string)
    end reverse

    My intro to programming used scheme (LISP variant), and we were about 6 weeks into the course before we stopped using strictly recursive techniques. My infinite all but dissappeared.

  6. #6
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    not bad, but "restof string" will need subString which the OP states cannot be used.

  7. #7
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    19

  8. #8
    faisalcmpm is offline Member
    Join Date
    Feb 2009
    Posts
    22
    Rep Power
    0

    Default

    Java Code:
    private String reverse(String string) {
    		String returnString =null;
    		if(string.length() == 1) {
    			returnString =  string;
    		} else {
    			returnString = String.valueOf((string.charAt(string.length() -1)));
    			returnString = returnString.concat(reverse(String.valueOf(string.subSequence(0, string.length() -1))));
    		}
    		return returnString;
    	}

  9. #9
    mtyoung is offline Senior Member
    Join Date
    Dec 2008
    Location
    Hong Kong
    Posts
    473
    Rep Power
    6

    Default

    subSequence...
    substring... , i think they functions the same... do not can use in the code or not

    Eranga said
    On a loop, get each character from the last index and append it into an empty string.
    that recursive function may intake 2 parameters, String and int
    int can indicate the starting pos(increment from 0 to length - 1) or ending pos (decrease from length - 1 to 0)
    return char or string with 1 length, or what ever you like

  10. #10
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    19

    Default

    Something like this.

    Java Code:
    private String getReversString(String str) {
    String temp = "";
    for(int i = 0; i < str.length(); i++) {
    try {
    temp = str.charAt(i) + temp;
    }
    catch(IndexOutOfBoundsException ex) {
    System.out.println("Index out of range exception found");
    }
    }
    return temp;
    }
    Ordering characters in reverse order. ;)

  11. #11
    faisalcmpm is offline Member
    Join Date
    Feb 2009
    Posts
    22
    Rep Power
    0

    Default

    This is correct.
    But his assignment is to bring up this without using
    1 for loop
    2 substring
    and the method should be recursively called

  12. #12
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    19

  13. #13
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    something like so:
    Java Code:
    public static String reverseString(String input, String output, int index)
    {
      if (index == 0)
      {
        return output;
      }
      else
      {
        output += input.charAt(index - 1);
        return reverseString(input, output, index - 1);
      }
    called with
    Java Code:
    String input = "Hello world!";
    String reverseString = reverseString(input, "", input.length());
    code not tested

  14. #14
    rdtindsm is offline Member
    Join Date
    Feb 2009
    Posts
    92
    Rep Power
    0

    Default

    The original post did call for recursion, and was later clarified with a specific function signature.

    emceenugget's method is IMHO, the best and correct method to solve the problem by adding a wrapper to call fubarable's method.

    Pedagogical insights:
    The use of helper methods.
    That a recursive formulation of a problem can give easily understood insights regarding the solution, even if loops are a better (less memory, limited stack frame) solution in the long term. (just reverse the rest of the list and add the head to the end).

    Let me also point out that passing the original string and an index is defining the "rest of the string", i.e., everything beyond the index. A substring method will work, so will passing an index (pointer) into the string.

    I don't know how substring actually works, but a string variable is usually a pointer, and substring could be implemented by simply returning the pointer to the position in an existing string, rather than creating a new string. That is, passing a string and a pointer (index) is a simple implementation of substring. This would particularly be true in C. i.e. substring = string + ndx with its null terminated strings.

    Don't want to be defensive, and I am, about any criticism of my previous post. fubarable understandably assumed an implementation I didn't state. Part of the scenery of forums, but I also think it is instructive to consider how these things work under the hood. Probably part of the point of the exercise.

    Would be an interesting experiment which I may do later. If I declare String str = new String("abcdef") (and forgive any syntax errors) what is the value of foo = substring(ndx,str). Is the value of foo reasonably close to str , or way off in a distant area of the heap? Does foo increment in a constant way for substring(ndx + 1), str)?

    So, my mind is racing trying to figure out the exact testing code, but, as I loved to see, that will be left as an exercise for the student.

  15. #15
    kathyla18 is offline Member
    Join Date
    Feb 2009
    Posts
    16
    Rep Power
    0

    Default

    i tested your code (Fubarable) and it works, but im supposed to use reverse(string) to call the method, and not
    reverseString(input, "", input.length());

  16. #16
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    Don't want to be defensive, and I am, about any criticism of my previous post. fubarable understandably assumed an implementation I didn't state. Part of the scenery of forums, but I also think it is instructive to consider how these things work under the hood. Probably part of the point of the exercise.
    Sorry about making assumptions about code not posted. You are correct, and I have nothing really to add to your previous well-written post.

  17. #17
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    6

    Default

    once again, just encase fubarable's method within one that fits your requirements.

  18. #18
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    19

    Default

    Quote Originally Posted by kathyla18 View Post
    i tested your code (Fubarable) and it works, but im supposed to use reverse(string) to call the method, and not
    reverseString(input, "", input.length());

    So the length validation of the original string and the temporary string object to store the return string declarations do inside the reverseString method.

Similar Threads

  1. how do i reverse this method for sorting?Again!
    By PureAwesomeness in forum New To Java
    Replies: 2
    Last Post: 03-09-2009, 12:51 AM
  2. [SOLVED] how do i reverse this method for sorting?
    By PureAwesomeness in forum New To Java
    Replies: 3
    Last Post: 03-08-2009, 09:37 PM
  3. Reverse and Replace a String in Linear Time
    By colin.cruise in forum New To Java
    Replies: 5
    Last Post: 07-01-2008, 09:02 PM
  4. How to use subString method
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-17-2008, 07:44 PM
  5. String substring function
    By ravian in forum New To Java
    Replies: 6
    Last Post: 01-02-2008, 07:35 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •