# 리트코드 344번 - Reverse String

zionhann·2022년 10월 6일
0 # Description

Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

# Examples

Example 1:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:

Input: s = ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

# Solution

class Solution {
public:
void reverseString(vector<char>& s) {
auto first = s.begin();
auto last = prev(s.end());

while (first < last) {
char temp = *first;
*first = *last;
*last = temp;

first++;
last--;
}
}
};

# Explanation

## Pseudocode

procedure reverseString(S)
B <- iterator to the beginning of S
E <- iterator to the last elemenet of S

while B < E do
swap B with E

B <- next(B)
E <- prev(E)
end while
end procedure

## Improvement

class Solution {
public:
void reverseString(vector<char>& s) {
int first = 0, last = s.size()-1;

while (first < last) {
swap(s[first++], s[last--]);
}
}
};

When accessing an element in a vector, using integer indices can reduce runtime. Furthermore, c++ provides std::swap() function in algorithm standard library.