Using recursion,only 1-line,but time exceeded


  • 0
    S
    public class Solution {
        public String reverseString(String s) {
            return s.length()<=1?s:(reverseString(s.substring(1))+s.charAt(0));
        }
    }

  • 2
    T

    Let's see what you crammed into that one line.
    (This is an excellent example that short code could be more inefficient than pages of code.)

    public String reverseString(String s) {
    	if (s.length() <= 1) {
    		return s; // base case, no op
    	} else {
    		StringBuilder builder = new StringBuilder();
    		// linear operation: copies String.value into String.value
    		String rest = s.substring(1); // skip first char
    		String reversedRest = reverseString(rest); // recursive call
    		// linear operation: copies String.value into StringBuilder.value
    		builder.append(reversedRest);
    		builder.append(s.charAt(0)); // append first char
    		// linear operation: copies StringBuilder.value into String.value
    		return builder.toString();
    	}
    }
    

    Let's see how many times the recursion is called: you start with a long string and do those linear operations. To get the reversed tail of the string you do a recursion with one shorter string which is still pretty long, but luckily it's decreasing. You'll end up with linear operations being executed n + n-1 + n-2 + n-3 + ... + 3 + 2 + 1 which is (from lower education) = n * (n-1) / 2 and you have a char-char copy 3 times, so you end up with O(n^2).


Log in to reply
 

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