Xác Nhận AnagramValid Anagram
Hiểu bài
Cho hai chuỗi ký tự s và t. Trả về true nếu t là anagram của s — tức là t được tạo bằng cách sắp xếp lại toàn bộ ký tự của s.
Ví dụ:
ts
s = "anagram", t = "nagaram"
output = true // cùng ký tự, khác thứ tự
s = "rat", t = "car"
output = false // 'r','a','t' ≠ 'c','a','r'Giả thiết: chỉ chứa ký tự thường tiếng Anh (a-z).
Hai chuỗi anagram phải có cùng độ dài.
Xem cách cơ bản (chậm hơn)
Cách cơ bản
O(n log n) time, O(n) spacets
function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) return false
// Sắp xếp cả hai chuỗi rồi so sánh
return s.split('').sort().join('') === t.split('').sort().join('')
}Vì sao cách này chậm:
Sắp xếp chuỗi dài n tốn O(n log n).
Cách này đơn giản nhưng chậm hơn cần thiết — Hash Map làm được trong O(n).
Lời giải tối ưu
Tối ưu
O(n) time, O(1) spacets
function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) return false
const count = new Map<string, number>()
// Đếm tần suất ký tự trong s
for (const ch of s) count.set(ch, (count.get(ch) ?? 0) + 1)
// Trừ tần suất theo t
for (const ch of t) {
const freq = count.get(ch)
if (!freq) return false // ký tự không có trong s hoặc đã dùng hết
count.set(ch, freq - 1)
}
return true
}Mấu chốt:
Đây là cách tối ưu: đếm tần suất ký tự của s vào Hash Map, rồi "tiêu hao" theo từng ký tự của t.
- Nếu ký tự nào đó thiếu hoặc bằng 0 → không phải anagram.
- Space thực tế O(1) vì chỉ có 26 ký tự a-z.
Chạy thử từng bước
Chạy thử qua từng bước — bấm vào một bước để xem dòng code tương ứng
1function isAnagram(s: string, t: string): boolean {2if (s.length !== t.length) return false3const count = new Map<string, number>()4// Đếm tần suất ký tự trong s5for (const ch of s) count.set(ch, (count.get(ch) ?? 0) + 1)6// Trừ tần suất theo t7for (const ch of t) {8const freq = count.get(ch)9if (!freq) return false // ký tự không có trong s hoặc đã dùng hết10count.set(ch, freq - 1)11}12return true13}
Trường hợp biên phải nhớ
Hai chuỗi rỗng — cùng độ dài 0, return true (xem là anagram của nhau).
Độ dài khác nhau — check ngay đầu, return false không cần duyệt.
Ký tự lặp nhiều lần: s="aab", t="baa" — count phải khớp chính xác tần suất.
Ký tự trong t nhiều hơn s: s="ab", t="aab" — freq của "a" về 0 rồi nhưng t còn dùng thêm → return false.