> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/string/344reverse-string.md).

# 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)$$

```python
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)$$

```python
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
```