# [344. Reverse String](https://leetcode.com/problems/reverse-string/description/?envType=daily-question&envId=2024-06-02)

# 1. Tóm tắt đề bài

Hãy viết một hàm `reverseString` nhận vào một mảng ký tự `s` và đảo ngược nó [tại chỗ](https://en.wikipedia.org/wiki/In-place_algorithm) với độ phức tạp bộ nhớ $O(1)$.

### Giới hạn

- $n =$ `s.length`
- $1 \le n \le 10^5$
- `s[i]` là [ký tự ASCII in được](https://vi.wikipedia.org/wiki/ASCII#K%C3%BD_t%E1%BB%B1_ASCII_in_%C4%91%C6%B0%E1%BB%A3c)

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(n)$**

> "Đời người thật ngắn ngủi, hãy dùng Python." - Một ai đó
> ```python
> def reverseString(self, s: List[str]) -> None:
> s.reverse()
> ```

Bỏ qua các rào cản về ngôn ngữ lập trình, thấy có xuất hiện **mảng**, **tại chỗ** và **bộ nhớ** $O(1)$ là ta nghĩ ngay đến vận dụng hai con trỏ.

# 3. Lời giải chi tiết

Khởi tạo hai con trỏ `left` trỏ đầu mảng, và `right` trỏ cuối mảng.

Ta từng bước swap ký tự tại `left` và `right` với nhau, sau đó tịnh tiến hai con trỏ dần đến giữa mảng, cho đến khi chúng trỏ về cùng một vị trí (`s.length` lẻ) hoặc vượt qua nhau (`s.length` chẵn).


### [Code mẫu](https://leetcode.com/problems/reverse-string/submissions/1274803841?envType=daily-question&envId=2024-06-02)

### Độ phức tạp thuật toán

Thời gian: $O(\frac{n}{2}) = O(n)$

Bộ nhớ mở rộng: $O(1)$

# 4. Kết luận & Gợi ý mở rộng

Hình như đầu tháng nên 2 bài cuối tuần nay nhắm mắt cũng làm được :sweat_smile:

Một số bài mở rộng:

- [541. Reverse String II](https://leetcode.com/problems/reverse-string-ii/description/)
- [345. Reverse Vowels of a String](https://leetcode.com/problems/reverse-vowels-of-a-string/)
- [151. Reverse Words in a String](https://leetcode.com/problems/reverse-words-in-a-string/)