242. Valid Anagram

Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:

https://leetcode.com/problems/valid-anagram/description/

Table of Contents

1. Cách tiếp cận vấn đề

2 chuỗi s và t cùng chỉ chứa ký tự thường, nên để giải được bài toán này, sẽ có 2 điểm chính cần lưu ý, từ đó cũng là mấu chốt để giải quyết vấn đề:

1. Một chuỗi được coi là anagram của chuỗi còn lại, khi chúng có cùng chính xác số lượng các chữ cái khác nhau, cũng như số lần xuất hiện của mỗi chữ cái. Ví dụ: String s = "hello" => Có 1 chữ h, 1 chữ e, 1 chữ o và 2 chữ l.
2. 2 chuỗi ký tự s và t giống nhau là một trường hợp đặc biệt của bài toán, lúc này t chính là "anagram" của s.

Từ đó chúng ta cũng sẽ có các cách làm chính xoay quanh việc tối ưu bộ nhớ hay tối ưu về mặt thời gian (luôn luôn mang tính trade-off)

2. Solution & Phân Tích

2.1. Sorting

Chúng ta có thể sắp xếp lần lượt 2 chuỗi s và t, sau đó chỉ cần kiểm tra xem 2 chuỗi đó có giống nhau hay không là được. Vì nếu chúng có cùng số lượng chữ cái cũng như số lần xuất hiện của mỗi chữ cái, thì sau khi sắp xếp, chúng sẽ chắc chắn bằng nhau.

Ví dụ: String s = "anagram", String t ="nagaram"

2 chuỗi sau khi sắp xếp sẽ có cùng giá trị: "aaagmnr"

Space Complexity: O(1) - không sử dụng thêm bất kỳ bộ nhớ nào

Time Complexity: O(nlogn) - thời gian tối ưu nhất khi sử dụng sorting

n: số lượng các ký tử của 2 chuỗi

2.2. Đếm sử dụng Map

Chúng ta sẽ tạo 1 map với key là kiểu ký tự (character) và value là kiểu số nguyên (int) đại diện cho số lần xuất hiện của ký tự key.

Chúng ta cần sử dụng 3 vòng lặp nhưng chúng tách biệt và không lồng nhau:

1. Duyệt qua từng ký tự của chuỗi s, tăng số lần xuất hiện của mỗi ký tự bằng việc tăng biến đếm (value) được lưu trữ tương ứng với mỗi ký tự (key) trong map đi 1 đơn vị.
2.  Duyệt qua từng ký tự của chuỗi t, giảm số lần xuất hiện của mỗi ký tự bằng việc giảm biến đếm (value) được lưu trữ tương ứng với mỗi ký tự (key) trong map đi 1 đơn vị.
3. Sau cùng, kiểm tra lại biến đếm (value) của tất cả các ký tự (key) trong map, nếu tất cả chúng đều bằng 0, hay tất cả các ký tự giữa 2 mảng đều triệt tiêu cho nhau, hay 2 mảng chứa cùng số lượng các chữ cái → Thì ta có thể kết luận được rằng chuỗi t là "anagram" của chuỗi s.

Space Complexity: O(n) - sử dụng map tương ứng với số lượng các ký tự

Time Complexity: O(3n) = O(n) sử dụng 3 vòng lặp rời nhau

n: số lượng các ký tử của 2 chuỗi

2.3. Đếm sử dụng Array

Về cơ bản thì logic sẽ giống hệt map, nhưng ta sẽ sử 1 mảng gồm 26 ô bộ nhớ, tương ứng với 26 ký tự trong bảng chữ cái alphabet, và 26 ô bộ nhớ này sẽ thay thế cho key ở solution với map.

Ta chỉ cần xác định ký tự đang duyệt là ở ô nhớ nào, sau đó tăng hoặc giảm giá trị tương ứng. Sau cùng, duyệt hết qua tất cả 26 ô nhớ và kiểm tra xem có giá trị nào khác 0 hay không, nếu có thì trả về false ngay lập tức, còn không có giá trị nào như vậy thì trả về true.

Mỗi ký tự sẽ có 1 mã số tương ứng trong bảng ASCII, từ "a" tới "z" sẽ có giá trị là từ 97 đến 122. Cách xác định thứ tự ô nhớ cho từng ký tự: ta sẽ lấy ký tự "a" làm chuẩn, sau đó trừ ký tự đang xét cho "a"

Space Complexity: O(n) - sử dụng map tương ứng với số lượng các ký tự

Time Complexity: O(3n) = O(n) sử dụng 3 vòng lặp rời nhau

n: số lượng các ký tử của 2 chuỗi

Vòng lặp đầu tiên cho chuỗi s:

Vòng lặp thứ hai cho chuỗi t:

Vòng lặp thứ ba cho mảng đếm:

Mảng thì chỉ có index và value, mình thêm hàng "Char" để dễ hình ký tự tương ứng với từng index.

3. Code

Mình sẽ sử dụng cách đếm với Array vì nó là một cách rất thông dụng khi làm việc với chuỗi chỉ chứa ký tự thường.