Resources

Question Source: Reverse String - LeetCode
Useful References:

Iterate append and delete: O(n²) / O(n)

Because of the del s[0] operation inside the while loop, the time complexity is O(n²)

class Solution:
    def reverseString(self, s):
        length = len(s)
        for i in range(len(s)-1,-1,-1):
            s.append(s[i])
        while length > 0:
            del s[0]
            length -= 1
        return s

s = Solution()
print(s.reverseString(["h", "e", "l", "l", "o"]))

Recursive Swap: O(n) / O(n)

class Solution:
    def reverseString(self, s):
        return self._recurse(s,0,len(s)-1)

    def _recurse(self, s, left, right):
        if left < right:
            s[left], s[right] = s[right], s[left]
            self._recurse(s, left+1, right-1)
        return s

s = Solution()
print(s.reverseString(["h", "e", "l", "l", "o"]))

⭐️ Two-Pointer Swap: O(n) / O(1)

class Solution:
    def reverseString(self, s):
        i = 0
        j = len(s)-1

        while i < j:
            s[i], s[j] = s[j], s[i]
            i += 1
            j -= 1
        return s

s = Solution()
print(s.reverseString(["h", "e", "l", "l", "o"]))

Slice: O(n) / O(n)

class Solution:
    def reverseString(self, s):
        s[:] = s[::-1]

`Reverse()` Function: O(n) / O(1)

The underlying implementation is using the swaps.

class Solution:
    def reverseString(self, s):
        s.reverse()

Table of Contents