Python cho người Việt

Python cho người Việt

Phỏng vấn: Tìm các từ cùng bộ ký tự

written by Nguyễn Thành Nam, on Mar 16, 2015 9:05:00 AM.

Câu hỏi

Cho một quyển từ điển D, và một từ W trong từ điển, yêu cầu xuất ra tất cả các từ có trong từ điển với cùng bộ ký tự như từ W.

Ví dụ từ mary có bộ ký tự là một chữ m, một chữ a, một chữ r và một chữ y, từ army cũng có cùng bộ ký tự như vậy.

Phân tích

Mối quan hệ giữa từ, và bộ ký tự là 1-n, tức là một từ sẽ có một bộ ký tự, nhưng một bộ ký tự có thể có nhiều từ. Do đó, cách giải bài này là thể hiện mối quan hệ giữa từ và bộ ký tự của nó.

Với mỗi từ X trong từ điển, ta sẽ tìm ra bộ ký tự K tương ứng của từ đó, và lưu X vào danh sách các từ có bộ ký tự K. Để trả lời câu hỏi, ta chỉ việc in ra danh sách các từ có bộ ký tự tương ứng với W.

Độ phức tạp thực thi của cách giải này là O(1) với O(n) bước xử lý trước (preprocessing), và tốn O(n) bộ nhớ.

from collections import defaultdict

def get_alphabet(word):
    count = defaultdict(int)
    for c in word:
        count[c] += 1
    # vì kiểu dict là khả biến, nên ta phải
    # chuyển "count" thành kiểu string để
    # có thể dùng làm khóa trong một dict khác
    r = []
    for k in sorted(count.keys()):
        r.append('%c%d' % (k, count[k]))
    return ''.join(r)

assert(get_alphabet('aaabb') == 'a3b2')

def solve(D, W):
    alpha_to_words = defaultdict(list)
    for word in D:
        alpha = get_alphabet(word)
        alpha_to_words[alpha].append(word)
    return alpha_to_words[get_alphabet(W)]

assert(solve(['mary', 'army', 'vithon'], 'mary') == ['mary', 'army'])

Cách giải trên sẽ áp dụng tốt nếu ta cần trả lời cho một loạt các từ W bởi vì ta chỉ tốn thời gian xử lý trước một lần, và sau đó có thể truy vấn alpha_to_words cho mỗi từ W sau đó. Tuy nhiên, nếu ta chỉ cần trả lời câu hỏi cho duy nhất một từ W thì việc tốn thêm O(n) bộ nhớ cho alpha_to_words là không cần thiết. Trong trường hợp đó, ta chỉ việc xét từng từ trong D, nếu nó có cùng bộ ký tự như W thì ta xuất nó ra ngay.