You get a string s. Return a new string with the characters of s in reverse order.
Solve it with recursion, a function that calls itself. Don't use a built-in reverse. A loop would work too, but this lesson is about the recursive call.
The string can be empty. Its reverse is then empty too, shown as "".
Example 1:
Input: s = "stressed" Output: "desserts" Explanation: The last letter, d, now comes first. The first letter, s, now comes last.
Example 2:
Input: s = "Room42" Output: "24mooR" Explanation: Digits and capital letters move like any other character.
Example 3:
Input: s = "" Output: "" Explanation: An empty string stays empty.
Constraints:
- 0 to 1,000 characters.
- Each character is an English letter or a digit.
Your solution should run in O(n) time, where n is the length of s.
Swap the first and the last character. The characters between them form a shorter string to reverse: the same problem.
Copy the characters into an array you can change. Give the recursive function two indexes, one for each end. When they meet or cross, nothing is left to swap.
Each call swaps two characters and moves both ends one step inward. That makes about n / 2 calls: O(n) time.
The characters and the calls waiting on the call stack take O(n) extra space.
Another way builds a new string at each call: the rest reversed, plus one character. It copies the characters again and again, which costs O(n2) time in most languages.
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check
