Sử dụng Counter() trong Python 3.x để tìm số ký tự xóa tối thiểu để làm hai chuỗi thành anagram

Trong bài viết này, chúng ta sẽ tìm hiểu về cách chúng ta có thể biến một chuỗi thành pangram sử dụng hàm counter() trong Python 3.x hoặc các phiên bản trước đó. Để làm vậy, chúng ta được phép xóa bất kỳ ký tự nào từ chuỗi đầu vào. Chúng ta cũng sẽ tìm số lượng ký tự cần xóa để biến chuỗi thành anagram.

Hai chuỗi được gọi là anagram của nhau khi chúng chứa cùng loại chữ cái theo bất kỳ thứ tự ngẫu nhiên nào.

Phương thức counter() có mặt trong module collections có sẵn trong Python. Điều kiện tiên quyết là import module collections để dùng hàm counter().

Thuật toán

1. Chuyển đổi chuỗi đầu vào thành kiểu dictionary có ký tự làm khóa và tần suất làm giá trị dùng Counter(inp_str) trong module collections.
2. Đếm tổng số khóa và đếm số khóa chung giữa hai dictionary chuyển từ chuỗi đầu vào.
3. Nếu không phát hiện khóa chung, nghĩa là cần xóa (tổng độ dài hai dictionary) ký tự từ cả hai chuỗi đầu vào.
4. Ngược lại (max(độ dài hai dictionary) - số khóa chung) sẽ cho số ký tự cần xóa.

collections.Counter là subclass của dictionary để đảm bảo đếm tự động các chữ cái bởi trình thông dịch. Chúng ta không thực sự cần tạo substring hoặc kiểm tra xem chúng có phải anagram thủ công.

Ví dụ

# Hai chuỗi thành anagram
from collections import Counter

def convertAnagram(str_1, str_2):
    # Chuyển chuỗi sang kiểu dictionary
    dict_1 = Counter(str_1)
    dict_2 = Counter(str_2)
    keys_1 = dict_1.keys()
    keys_2 = dict_2.keys()
    # Đếm số khóa trong cả hai list khóa
    count_1 = len(keys_1)
    count_2 = len(keys_2)
    # Chuyển cặp khóa thành set để tìm khóa chung
    set_1 = set(keys_1)
    commonKeys = len(set_1.intersection(keys_2))
    if (commonKeys == 0): # không tìm thấy chung, tức là tất cả đều khác nhau
        return (count_1 + count_2)
    else: # một số phần tử đã khớp trong đầu vào
        return (max(count_1, count_2) - commonKeys)

str_1 = 'Tutorials'
str_2 = 'sTutalori'
str_3 = 'Point'
print(convertAnagram(str_1, str_2))
print(convertAnagram(str_3, str_2))

Kết quả

0
6

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu cách chúng ta có thể làm cho hai chuỗi trở thành anagram của nhau bằng cách đếm số ký tự cần thiết để duy trì mối quan hệ anagram trong Python 2.x.