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ụ:
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)
O(n log n) time, O(n) spacefunction 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('')
}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
O(n) time, O(1) spacefunction 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
}Đâ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
- 1
s="cat", t="act".
Độ dài bằng nhau (3=3) → tiếp tục.
s:"cat"t:"act"sameLength:true - 2
Đếm tần suất ký tự của s="cat": count = {c:1, a:1, t:1}.
phase:"đếm s"count:{"c":1,"a":1,"t":1} - 3
t[0]="a": count["a"]=1 (>0) → giảm còn 0.
ch:"a"count:{"c":1,"a":0,"t":1} - 4
t[1]="c": count["c"]=1 (>0) → giảm còn 0.
ch:"c"count:{"c":0,"a":0,"t":1} - 5
t[2]="t": count["t"]=1 (>0) → giảm còn 0.
Hết vòng lặp, không ký tự nào thiếu → return true.
ch:"t"count:{"c":0,"a":0,"t":0}result:true
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.