When establishing a foundation, do not overly rely on library functions.
# 344. Reverse String
LeetCode Problem Link (opens new window)
Write a function that reverses a given string. The input string is provided as an array of characters, char[].
Do not allocate extra space for another array; you must modify the input array in place with O(1) extra space.
You may assume all the characters in the array are printable ASCII.
Example 1:
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:
Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
# Approach
Let's start with a bit of a digression:
For this problem, some students might directly use a library function such as reverse in C++ to solve it immediately. Every programming language presumably has such library functions.
If you tackle problems this way, you won't grasp the underlying principles of how reversing a string is implemented.
However, I'm not saying library functions can't ever be used; it depends on the context.
During a live interview, when do we use library functions and when do we avoid them?
If the key part of the problem can be solved with a library function alone, it is advisable not to use the library function.
Clearly, the interviewer is not testing your familiarity with library functions. This is especially crucial for those using Python and Java, as they provide a very rich set of library functions.
If the library function is merely a small part of the solution process and you are well aware of its internal implementation principles, then you may consider using the library function.
It is recommended that you adopt such a principle when practicing algorithms on LeetCode, as it will help you understand the algorithms better.
Avoid getting lost in solving problems with a single line of code using library functions and similar techniques — not that these techniques are bad, but you should use them when having a bit of fun.
When writing the implementation yourself, ensure you understand how to achieve the corresponding functionality.
Now, let's talk about reversing a string.
You might recall that we have already discussed 0206.Reverse Linked List (opens new window).
In reversing a linked list, we used the two-pointer technique.
Reversing a string also uses the two-pointer technique, but reversing a string is actually simpler than reversing a linked list.
Since a string is essentially an array, its elements are distributed contiguously in memory, which means that there is still a difference in approach when comparing reversing a linked list with reversing a string.
If you are not clear about the principles of arrays and linked lists, you can refer to these articles: Linked List Basics (opens new window), Array Theory Basics (opens new window).
For a string, we define two pointers (or you can think of them as index positions), one starting from the beginning of the string and the other starting from the end. The two pointers move towards the center and swap the elements.
Take the string hello as an example, the process is as follows:
It's not difficult to write the following C++ code:
void reverseString(vector<char>& s) {
for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
swap(s[i],s[j]);
}
}
2
3
4
5
Inside the loop, just swap s[i] and s[j]. I've used the swap function from the library here. It is a permissible choice because the implementation of the swap operation is generally well-known, and this library function is only a part of the solution. Therefore, using this library function is also acceptable.
There are two ways to implement a swap.
One with the typical value-swapping:
int tmp = s[i];
s[i] = s[j];
s[j] = tmp;
2
3
Another using bit manipulation:
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
2
3
This problem is relatively simple but provides an opportunity to discuss the principles of using library functions while practicing.
If the key part of the problem can be solved directly with a library function alone, it's advisable not to use it.
If the library function is just a part of the problem-solving process and you fully understand the internal implementation principles, you can consider using it.
Based on these principles, I haven't used the reverse library function, but I did use swap.
In string-related problems, library functions can be very tempting because of the various operations like reversing, slicing, and word splitting — that’s why string library functions are so abundant.
Following the principles mentioned earlier, you might find it beneficial to apply them to string-related problems, yielding both a methodical choice and added insight.
Here's the C++ code:
class Solution {
public:
void reverseString(vector<char>& s) {
for (int i = 0, j = s.size() - 1; i < s.size()/2; i++, j--) {
swap(s[i],s[j]);
}
}
};
2
3
4
5
6
7
8
- Time Complexity: O(n)
- Space Complexity: O(1)
# Versions in Other Languages
# Java:
class Solution {
public void reverseString(char[] s) {
int l = 0;
int r = s.length - 1;
while (l < r) {
s[l] ^= s[r]; // Compute a ^ b and place it in a
s[r] ^= s[l]; // XOR the result with b and store in b, now b = a, a = a ^ b
s[l] ^= s[r]; // XOR the result with a and store in a, now b = a, a = b, swap complete
l++;
r--;
}
}
}
// The second method using temp for value swapping is more comprehensible to many
class Solution {
public void reverseString(char[] s) {
int l = 0;
int r = s.length - 1;
while(l < r){
char temp = s[l];
s[l] = s[r];
s[r] = temp;
l++;
r--;
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Python:
(Version 1) Two Pointers
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left, right = 0, len(s) - 1
# This approach doesn't need to check for odd or even lengths.
# It's tested and has a lower time and space complexity than using for i in range(len(s)//2).
# The while loop needs to check the condition each time, while the range function generates numbers directly, offering better time complexity. Thus, using range is recommended.
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
2
3
4
5
6
7
8
9
10
11
12
13
14
(Version 2) Using a Stack
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
stack = []
for char in s:
stack.append(char)
for i in range(len(s)):
s[i] = stack.pop()
2
3
4
5
6
7
8
9
10
(Version 3) Using Range
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
n = len(s)
for i in range(n // 2):
s[i], s[n - i - 1] = s[n - i - 1], s[i]
2
3
4
5
6
7
8
(Version 4) Using Reversed
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s[:] = reversed(s)
2
3
4
5
6
(Version 5) Using Slicing
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s[:] = s[::-1]
2
3
4
5
6
(Version 6) Using List Comprehension
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
s[:] = [s[i] for i in range(len(s) - 1, -1, -1)]
2
3
4
5
6
(Version 7) Using reverse()
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
# In-place reversal, no return value
s.reverse()
2
3
4
5
6
7
# Go:
func reverseString(s []byte) {
left := 0
right := len(s)-1
for left < right {
s[left], s[right] = s[right], s[left]
left++
right--
}
}
2
3
4
5
6
7
8
9
# JavaScript:
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function(s) {
// Do not return anything, modify s in-place instead.
reverse(s)
};
var reverse = function(s) {
let l = -1, r = s.length;
while(++l < --r) [s[l], s[r]] = [s[r], s[l]];
};
2
3
4
5
6
7
8
9
10
11
12
13
# TypeScript:
/**
Do not return anything, modify s in-place instead.
*/
function reverseString(s: string[]): void {
let length: number = s.length;
let left: number = 0,
right: number = length - 1;
let tempStr: string;
while (left < right) {
tempStr = s[left];
s[left] = s[right];
s[right] = tempStr;
left++;
right--;
}
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Swift:
// Two pointers - Tuple
func reverseString(_ s: inout [Character]) {
var l = 0
var r = s.count - 1
while l < r {
// Using tuple
(s[l], s[r]) = (s[r], s[l])
l += 1
r -= 1
}
}
2
3
4
5
6
7
8
9
10
11
# Rust:
impl Solution {
pub fn reverse_string(s: &mut Vec<char>) {
let (mut left, mut right) = (0, s.len()-1);
while left < right {
let temp = s[left];
s[left] = s[right];
s[right] = temp;
left += 1;
right -= 1;
}
}
}
2
3
4
5
6
7
8
9
10
11
12
# C:
void reverseString(char* s, int sSize){
int left = 0;
int right = sSize - 1;
while(left < right) {
char temp = s[left];
s[left++] = s[right];
s[right--] = temp;
}
}
2
3
4
5
6
7
8
9
10
# C#:
public class Solution
{
public void ReverseString(char[] s)
{
for (int i = 0, j = s.Length - 1; i < j; i++, j--)
{
(s[i], s[j]) = (s[j], s[i]);
}
}
}
2
3
4
5
6
7
8
9
10
# PHP:
// Two pointers
// One:
function reverseString(&$s) {
$left = 0;
$right = count($s)-1;
while($left<$right){
$temp = $s[$left];
$s[$left] = $s[$right];
$s[$right] = $temp;
$left++;
$right--;
}
}
// Two:
function reverseString(&$s) {
$this->reverse($s,0,count($s)-1);
}
// Swap elements from specified positions
function reverse(&$s, $start, $end) {
for ($i = $start, $j = $end; $i < $j; $i++, $j--) {
$tmp = $s[$i];
$s[$i] = $s[$j];
$s[$j] = $tmp;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Scala:
object Solution {
def reverseString(s: Array[Char]): Unit = {
var (left, right) = (0, s.length - 1)
while (left < right) {
var tmp = s(left)
s(left) = s(right)
s(right) = tmp
left += 1
right -= 1
}
}
}
2
3
4
5
6
7
8
9
10
11
12