LeetCode #344 Reverse String

Easy

Problem

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

Iterate string character until meet middle item.

It’s noted that we can use XOR to swap if it’s not allowed to use built-in swap function.

# XOR swap
a = a ^ b
b = a ^ b = (a ^ b) ^ b = a
a = a ^ b = (a ^ b) ^ a = b

Complexity

For will be finished after encountering middle item, which takes O(n/2) time if n denotes to length of string. Hence, time complexity is O(n).

And it only uses O(1) extra space.