Java - Is recursion not an efficient solution?


  • 0
    E

    I know there are different solutions for this problem but why is a recursive solution so slow? I get Time Limit Exceeded error using the following solution. Is there anyway to speed it up?

    public class Solution {
        public String reverseString(String s) {
            if(s.length() == 0 || s.length() == 1) return s;
            int length = s.length();
            return s.substring(length-1) + reverseString(s.substring(0, length-1));
        }
    }
    

  • 1

    @ensiferum

    • substring is always a time-consuming operation
    • even length method in your solution is quite costly - O(n^2)
    • recursive invoking is rather slow when there is too many of them

    There is totally no need to adopt recursive method in this problem.


  • 0
    E

    Thanks so much for the explanation @LHearen! For some reason I was avoiding using any additional space. I changed the solution to this and got accepted.

    public class Solution {
        public String reverseString(String s) {
            char[] strChars = s.toCharArray();
            int j = s.length() - 1;
            for(int i = 0; i <= j; i ++) {
                char temp = strChars[i];
                strChars[i] = strChars[j];
                strChars[j] = temp;
                j--;
            }
            return new String(strChars);
        }
    }
    

  • 0

    @ensiferum I don't know too much about what can be done in java but in C/C++, it can be simple as follows, an in-place method.

    class Solution {
    public:
        string reverseString(string s) 
        {
            int len = s.length();
            for(int i = 0; i < len/2; ++i)
                swap(s[i], s[len-i-1]);
            return s;
        }
    };
    

  • 0

    @LHearen said in Java - Is recursion not an efficient solution?:

    even length method in your solution is quite costly - O(n^2)

    What do you mean? Sounds wrong.


  • 0

    @StefanPochmann In each invoked method, it will measure the length of the string to access the last character, I don't know what is going on in Java but C/C++, this will traverse the whole string until the \0, so that's where it takes O(n). Is it right in Java?

    int length = s.length();


  • 0

    @LHearen Neither Java's String nor C++'s string traverse the string to measure the length. They take O(1).


  • 0

    @StefanPochmann I just checked it in recent version C++11 the time complexity is constant while the formers are O(n). I misunderstood it as strlen in C now. Thanks for your reminding!

    But even we just ignore this part, the substring can also cost O(n) each time till the end and as a result the cost will also be O(n^2), right?


  • 1

    @LHearen said in Java - Is recursion not an efficient solution?:

    the formers are O(n)

    That's not the C++ library. That's some other string implementation.

    Apparently it wasn't explicitly specified to be O(1) before C++11, but I'm sure O(1) was the de-facto standard for many years before (if not always). See for example this StackOverflow question from 2008 and its answers (one guy even argued that it had to have been O(1), though I can't understand the whole argument because I don't know "ropes").

    Edit: Yes, substring takes linear time and makes the solution use quadratic time. Honestly I'm surprised it got TLE, though, I would've expected MLE. Maybe they're optimizing under the hood, using the immutability of Java string to share the data?


  • 0
    E

    @StefanPochmann Sorry I am new here. I am assuming by TLE you meant Time Limit Exceeded, but what does MLE means? And what is the difference?

    Also appreciate your inputs!


  • 0

    @ensiferum Memory Limit Exceeded.


  • 1

    @StefanPochmann I re-checked the complexity issue just now, here is a official document clearly pointing it out that it should be O(1) as you argued. Thank you, man...always learn something from you these days!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.