344_Reverse String

[easy] [string, two pointers]

Write a function that takes a string as input and returns the string reversed.

Example 1:

Input: "hello"
Output: "olleh"

Example 2:

Input: "A man, a plan, a canal: Panama"
Output: "amanaP :lanac a ,nalp a ,nam A"

Solution 1: two pointers

Idea:

• First convert the string into a list. Loop from the beginning and from the end simultaneously. Invert the letters at symmetric places. For example, invert the first and the last letter, then second first and second last letter....

Time Complexity: $O(n)$

Space Complexity: $O(n)$

def reverseString(s):
    """
    :type s: str
    :rtype: str
    """

    # convert to list
    l = list(s)
    # two pointer
    i , j = 0, len(l)-1
    # invert letters at symmetric places
    while i < j :
        l[i], l[j] = l[j], l[i]
        i += 1
        j -= 1
    return "".join(l)


# simpler code
def reverseString(s):
    """
    :type s: str
    :rtype: str
    """
    ls = list(s)
    for i in range(len(ls)//2):
        ls[i], ls[~i] = ls[~i], ls[i]
    return "".join(ls)

Solution 2: recursive

Idea:

• For a given string, divide into two sub string with similar length, reverse the position of two substring first and then reverse letters in each substring using recursive function.

Time Complexity: $O(n)$ depth of the recursion tree is $log_2 n$, number of leaves in the lowest level is $n = 2^{log_2 n}$, thus total time complexity is $1 + 2^1 + 2^2 + ... + 2^{\log_2{n}} = O(n)$

Space Complexity: $O(n)$

def reverseString(s):
    """
    :type s: str
    :rtype: str
    """
    n = len(s)
    # define base case
    if n <= 1 :
        return s
    # recursive
    out = reverseString(s[n/2:]) + reverseString(s[:n/2])
    return out