Using recursion,only 1-line,but time exceeded

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

• 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)`.

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