Group Anagrams

Q: Độ phức tạp thời gian của bài toán nhóm các từ đảo chữ là bao nhiêu?

Việc tạo các khóa gồm chữ cái đã sắp xếp mất O(n · k log k) với n từ có tối đa k chữ cái, còn thao tác trên map mất O(n · k) . Sắp xếp các từ để sắp thứ tự đầu ra tốn thêm O(n · k · log n) , đây là phần chi phối. Cần O(n · k) bộ nhớ cho các khóa và các nhóm.

Trung bìnhBăm Sắp xếp

+10

Bạn nhận được một danh sách các từ strs. Hai từ là từ đảo chữ khi một từ có thể được tạo thành bằng cách sắp xếp lại các ký tự của từ kia, mỗi ký tự xuất hiện cùng số lần. Gom mỗi từ cùng tất cả các từ đảo chữ của nó, rồi trả về một chuỗi cho mỗi nhóm: các từ trong nhóm được sắp xếp theo thứ tự bảng chữ cái và nối với nhau bằng một dấu cách. Sắp xếp các nhóm theo thứ tự bảng chữ cái dựa trên từ đầu tiên của mỗi nhóm.

Một từ lặp lại sẽ xuất hiện hai lần trong nhóm của nó, còn một từ không có từ đảo chữ sẽ tạo thành một nhóm chỉ có một từ. Thứ tự bảng chữ cái ở đây là thứ tự trong từ điển: aab đứng trước ab, và ab đứng trước abc.

Hàm

groupAnagrams(strs: string-array) → string-array

strsstring-array: các từ cần nhóm, chỉ dùng chữ cái viết thường
Trả vềstring-array: mỗi nhóm một chuỗi: các từ trong chuỗi được sắp xếp rồi nối bằng dấu cách, các nhóm được sắp xếp theo từ đầu tiên

Ràng buộc

1 ≤ strs.length ≤ 4000
1 ≤ strs[i].length ≤ 8
Mỗi từ chỉ chứa các chữ cái tiếng Anh viết thường.

Ví dụ

Đầu vào: strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]
Đầu ra: ["apple", "enlist listen silent", "notes onset stone tones"]
Giải thích: enlist, listen và silent mỗi từ sử dụng các chữ cái e, i, l, n, s và t một lần. notes, onset, stone và tones có chung các chữ cái e, n, o, s và t. apple không khớp với từ nào và đứng đầu theo thứ tự từ.

Đầu vào: strs = ["race", "arc", "care", "car", "acre"]
Đầu ra: ["acre care race", "arc car"]
Giải thích: acre, care và race có chung các chữ cái a, c, e và r. arc và car không có chữ e, nên chúng tạo thành nhóm riêng. acre đứng trước arc vì c đứng trước r ở vị trí chữ cái thứ hai.

Đầu vào: strs = ["b", "a", "b"]
Đầu ra: ["a", "b b"]
Giải thích: Hai bản sao của b là hai từ đảo chữ của nhau và cả hai đều nằm trong nhóm. a không có từ nào ghép cặp với nó và đứng đầu.

Câu hỏi mở rộng

Nếu các từ có thể chứa bất kỳ ký tự Unicode nào, cách nào vẫn hiệu quả: sắp xếp các chữ cái hay đếm số lần xuất hiện của từng chữ cái, và bạn sẽ thay đổi cách đó như thế nào?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Tính khóa từ riêng từng từ sao cho khóa giống nhau với mọi từ đảo chữ của từ đó và khác với mọi từ khác. Các chữ cái của một từ khi được sắp xếp sẽ tạo thành khóa như vậy, còn một bản đồ băm ánh xạ khóa đến nhóm sẽ gom các nhóm chỉ trong một lượt. Hãy sắp xếp các từ trước để có ngay thứ tự cần thiết.

So sánh từng từ với mọi nhóm

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Giữ một danh sách các nhóm và so sánh mỗi từ với từ đầu tiên của từng nhóm. Quan hệ đảo chữ có tính bắc cầu, nên chỉ cần so sánh một lần với mỗi nhóm là đủ để quyết định từ đó có thuộc nhóm hay không. Hai từ là từ đảo chữ khi chúng có cùng độ dài và số lần xuất hiện của mỗi trong 26 chữ cái đều bằng nhau. Hãy sắp xếp đầu vào trước: khi đó, mỗi nhóm sẽ được điền theo thứ tự bảng chữ cái và các nhóm được tạo theo thứ tự từ đầu tiên của chúng.

Khi không có hai từ nào là từ đảo chữ của nhau, mỗi từ phải được so sánh với tất cả các nhóm đứng trước nó: 4000 từ tạo ra khoảng 8 × 10^6 phép so sánh, mỗi phép so sánh kiểm tra tối đa 8 ký tự và 26 bộ đếm.

Thuật toán

Sắp xếp các từ theo thứ tự bảng chữ cái.
Với mỗi từ, tìm một nhóm có từ đầu tiên có số lượng từng chữ cái giống nhau rồi thêm từ đó vào nhóm. Nếu không có nhóm nào phù hợp, hãy tạo một nhóm mới.
Trả về các từ trong mỗi nhóm, nối với nhau bằng một dấu cách, theo thứ tự tạo nhóm.

def is_anagram(a, b):
    # Same length, and every letter appears as often in a as in b.
    if len(a) != len(b):
        return False
    counts = [0] * 26
    for c in a:
        counts[ord(c) - 97] += 1
    for c in b:
        counts[ord(c) - 97] -= 1
    return all(x == 0 for x in counts)


def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = []
    for word in sorted(strs):
        for group in groups:
            if is_anagram(group[0], word):
                group.append(word)
                break
        else:
            groups.append([word])
    return [" ".join(group) for group in groups]

Nhóm theo các chữ cái đã sắp xếp trong bản đồ băm

Ý tưởng

Tính tên của nhóm từ chính từ từ đó. Sắp xếp các chữ cái của một từ, rồi mọi từ đảo chữ của nó sẽ cho cùng một chuỗi: listen, silent và enlist đều trở thành eilnst, còn stone trở thành enost. Hai từ có cùng dạng đã sắp xếp khi và chỉ khi chúng có cùng các chữ cái với số lần xuất hiện như nhau, đó là định nghĩa của từ đảo chữ. Sau đó, dùng bản đồ băm ánh xạ khóa tới danh sách từ để nhóm tất cả từ chỉ trong một lượt, không cần so sánh từ này với các từ thuộc nhóm khác.

Thứ tự được giữ nguyên bằng cách sắp xếp đầu vào trước, như cách làm trước đó: mỗi danh sách được điền theo thứ tự bảng chữ cái, và một khóa được thêm vào bản đồ khi từ đầu tiên của nhóm đó xuất hiện. Bản đồ giữ thứ tự chèn sẽ trả về các nhóm theo thứ tự đó; nếu không, hãy giữ các nhóm trong một danh sách và ánh xạ mỗi khóa tới chỉ số của nhóm.

Sắp xếp đầu vào cần khoảng 5 × 10^4 phép so sánh từ cho 4000 từ, thay vì 8 × 10^6.

Thuật toán

Sắp xếp các từ theo thứ tự bảng chữ cái.
Với mỗi từ, tạo khóa bằng cách sắp xếp các ký tự của từ đó.
Tra khóa trong bảng băm. Nếu khóa chưa có, tạo một nhóm trống cho khóa đó và giữ các nhóm theo thứ tự bạn tạo.
Thêm từ vào nhóm của khóa đó.
Trả về các từ trong mỗi nhóm, nối với nhau bằng một dấu cách, các nhóm theo thứ tự được tạo.

def groupAnagrams(strs):
    # Sort first: each group fills up in alphabetical order,
    # and groups are created in the order of their first word.
    groups = {}  # key (the letters in sorted order) -> the group's words
    for word in sorted(strs):
        key = "".join(sorted(word))
        groups.setdefault(key, []).append(word)
    # A dict keeps insertion order, so the groups come out by first word.
    return [" ".join(words) for words in groups.values()]

Lỗi thường gặp và trường hợp biên

Sắp xếp các nhóm theo khóa thay vì theo từ đầu tiên. Với ["cab", "bad"], các khóa abc và abd khiến cab đứng trước, nhưng bad mới nên đứng đầu.
Thu thập các từ vào tập hợp (set). ["b", "a", "b"] phải cho kết quả b b; tập hợp chỉ giữ lại một bản sao.
Tạo khóa chỉ từ các chữ cái khác nhau. ab và aabb dùng cùng hai chữ cái nhưng không phải là từ đảo chữ của nhau.
Sắp xếp từng nhóm nhưng không sắp xếp đầu vào và cũng không sắp xếp các nhóm. Khi đó, thứ tự chèn sẽ tuân theo đầu vào chứ không phải các từ đầu tiên.

Câu hỏi thường gặp3

Độ phức tạp thời gian của bài toán nhóm các từ đảo chữ là bao nhiêu?

Việc tạo các khóa gồm chữ cái đã sắp xếp mất O(n · k log k) với n từ có tối đa k chữ cái, còn thao tác trên map mất O(n · k). Sắp xếp các từ để sắp thứ tự đầu ra tốn thêm O(n · k · log n), đây là phần chi phối. Cần O(n · k) bộ nhớ cho các khóa và các nhóm.

Dùng khóa đếm chữ cái có nhanh hơn sắp xếp từng từ không?

Một khóa đếm, tức 26 số lượng chữ cái được viết thành văn bản như 1#0#2#…, tốn O(k) thay vì O(k log k), nên nhanh hơn với những từ dài. Với từ có 8 chữ cái trở xuống, cách sắp xếp cũng nhanh tương đương. Cả hai khóa đều chính xác: hai từ có số lượng từng chữ cái giống nhau khi và chỉ khi chúng có các chữ cái được sắp xếp giống nhau.

Tại sao không dùng tổng mã ký tự làm khóa?

Các chữ cái khác nhau có thể cho cùng một tổng: a + d bằng b + c, vì vậy ad và bc sẽ thuộc cùng một nhóm. Tích của một số nguyên tố cho mỗi chữ cái là chính xác, nhưng dùng 101 cho z khiến một từ gồm mười chữ z bị tràn số nguyên 64 bit.

def groupAnagrams(strs):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

strs = ["listen", "stone", "silent", "notes", "enlist", "onset", "tones", "apple"]

Đầu ra mong đợi

["apple", "enlist listen silent", "notes onset stone tones"]