# Solution by ananai

• #### Approach #1 std::reverse [Accepted]

Algorithm

Apply `std::reverse` on a string.

``````string reverseString(string s) {

reverse(s.begin(), s.end());

return s;
}
``````

Complexity Analysis

• Time complexity : \$\$O(n)\$\$.

`reverse` function works in linear time.

• Space complexity : \$\$O(1)\$\$.

#### Approach #2 Iterative [Accepted]

Algorithm

Iterate through a half of the string each time swap mirror elements, i.e. first and last elements etc.

``````leetcode
*      *
eeetcodl
*    *
edetcoel
*  *
edotceel
**
edocteel
``````
``````string reverseString(string s) {

for(int i = 0; i<s.length()/2; i++) {
swap(s[i], s[s.length()-1-i]);
}

return s;
}
``````

Complexity Analysis

• Time complexity : \$\$O(n)\$\$.

Every swap during iteration takes \$\$O(1)\$\$ time, total \$\$O(n)\$\$.

• Space complexity : \$\$O(1)\$\$.

#### Approach #3 Recursive Divide and Conquer [Accepted]

Algorithm

Keep dividing the string into halves and concatenate swapped halves.

``````reverseString("et") + reverseString("le")
(reverseString("t") + reverseString("e")) + (reverseString("l") + reverseString("e"))
(("t") + ("e")) + (("e") + ("l"))
``````
``````string reverseString(string s) {

int l = s.length();

if (l<2) {
return s;
}

return reverseString(s.substr(l/2)) + reverseString(s.substr(0, l/2));
}
``````

Complexity Analysis

• Time complexity : \$\$O(n)\$\$.

Concatenation each time takes \$\$O(1)\$\$ making overall \$\$O(n)\$\$ time.

• Space complexity : \$\$O(logn)\$\$.

#### Approach #4 Recursive Naive [Memory Limit Exceeded]

Algorithm

Get first character of the string and put it to the end. Call recursion of remaining substring.

``````reverseString("code")
(reverseString("ode")) + "c"
((reverseString("de")) + "o") + "c"
(((reverseString("e") + "d") + "o") + "c"
((("e") + "d") + "o") + "c"
``````
``````string reverseString(string s) {

if(s.length() == 0) {
return s;
}

return reverseString(s.substr(1)) + s[0];
}
``````

Complexity Analysis

• Time complexity : \$\$O(n)\$\$.

Concatenation each time consume \$\$O(1)\$\$ making overall \$\$O(n)\$\$ time.

• Space complexity : \$\$O(n)\$\$.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.