Pattern · Hash MapTrung bình
Nhóm Các AnagramGroup Anagrams
Hiểu bài
Cho bạn một mảng chuỗi strs. Nhóm các chuỗi là anagram của nhau lại với nhau. Trả về danh sách các nhóm (thứ tự trong mỗi nhóm và thứ tự giữa các nhóm không quan trọng).
Ví dụ:
ts
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
output = [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
// "eat", "tea", "ate" cùng nhóm vì đều là anagram của "aet"
// "tan", "nat" cùng nhóm vì đều là anagram của "ant"
// "bat" đứng một mìnhBài yêu cầu tìm "chữ ký" (key) chung của các anagram.
Có 2 cách tạo key: sắp xếp từ hoặc đếm tần suất ký tự.
Cách cơ bản
O(n² · k log k) time, O(n) spacets
function groupAnagrams(strs: string[]): string[][] {
const groups: string[][] = []
const visited = new Set<number>()
for (let i = 0; i < strs.length; i++) {
if (visited.has(i)) continue
const group = [strs[i]]
const sorted = strs[i].split('').sort().join('')
for (let j = i + 1; j < strs.length; j++) {
if (visited.has(j)) continue
if (strs[j].split('').sort().join('') === sorted) {
group.push(strs[j])
visited.add(j)
}
}
groups.push(group)
}
return groups
}Vì sao cách này chậm:
Hai vòng lặp lồng nhau, mỗi so sánh tốn O(k log k) để sắp xếp chuỗi dài k.
Hash Map giảm xuống một vòng lặp duy nhất O(n).
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.