I am trying to reverse a string recursively in Python, however, this solution does not work
def reverseString(self, s):
"""
:type s: List[str]
:rtype: None Do not return anything, modify s in-place instead.
"""
if len(s) == 0:
return s
s[0], s[-1] = s[-1], s[0]
self.reverseString(s[1:-1])
For the sample input ["h","e","l","l","o"], I get the output ["o","e","l","l","h"]. Can anyone exlpain why this does not work?
def reverse(s):
if len(s) == 0:
return s
return reverse(s[1:]) + s[0]
Your base condition is correct. But, your recursive call is complicated and not incorrect.
def reverse(s):
if len(s) == 0:
return ""
return s[-1] + reverse(s[:-1])
s = ["h","e","l","l","o"]
[letter for letter in reverse(s)] # prints ['o', 'l', 'l', 'e', 'h']
You are trying to swap the first and last elements, then the second and last before element and so on. You should also consider the case when there are odd number of elements, you end up with the base case of having just 1 element, hence you need to include the base case for len(s) == 0 or len(s)==1.
I have fixed your code below :
def reverse(s):
if len(s) == 0 or len(s)==1:
return s
return s[-1] + reverse(s[1:-1]) + s[0]
[item for item in reverse(''.join(s))] # prints ['o', 'l', 'l', 'e', 'h']
The problem with your code is that reverseString(s[1:-1]) creates a new copy of the list, and what you do to that has no effect on the list in the current level of recursion.
You can reconstruct the string with the first and last characters swapped and the inside part reversed and return that from each level:
def reverseString(s):
if len(s) <= 1:
return s
return s[-1] + reverseString(s[1:-1]) + s[0]
print(reverseString('hello'))
Output:
olleh
s[0], s[-1] = s[-1], s[0]
This modifies the input list. It appears that your intent is to swap two values in the input with a given call, and use recursion to cover each needed pair of values.
self.reverseString(s[1:-1])
This makes a recursive call on a newly created list, and ignores the result. It does not swap any more contents from the original list.
There is no reason to modify the input in-place. It doesn't make for a simple solution, and it limits the kinds of sequences you can handle. In general, you want recursive functions to produce new values, and leave their inputs alone - it's much easier to reason about them this way. (Plus you get to handle strings and tuples automatically.)
One simple approach is: we recognize that the first character of the input should come last in the output, and then we can get the rest of the string by reversing the rest of the input - which we can do by making a recursive call on the rest of the input. This leads naturally to @HarshalParekh's solution.
