Hướng dẫn fun with anagrams python - vui vẻ với con trăn đảo ngữ

Câu hỏi là: Cho một loạt các chuỗi, xóa từng chuỗi là một cách của một chuỗi trước đó, sau đó trả về mảng còn lại theo thứ tự được sắp xếp.

Ví dụ str = ['code', 'doce', 'ecod', 'framer', 'frame']]]]]

Mã và Doce là đảo chữ. Hủy bỏ Doce khỏi mảng và giữ mã xuất hiện đầu tiên trong mảng.

Mã và ECOD là đảo chữ. Hủy bỏ ECOD khỏi mảng và giữ mã xuất hiện đầu tiên trong mảng.

Mã và framer không phải là đảo chữ. Giữ cả hai chuỗi trong mảng.

Framer và khung không phải là đảo chữ do r trong framer. Giữ cả hai chuỗi trong mảng.

Đặt hàng các chuỗi còn lại theo thứ tự tăng dần: ['mã', 'khung', 'framer'].

Mã giải pháp là:

def checkForAnagrams(word, arr):
    # Checking if the word has an anagram in the sliced array.
    for x in arr:
        if (sorted(word) == sorted(x)):
            return True
    return False
            
def funWithAnagrams(text):
    limit = len(text)
    text.reverse()
    # Creating a copy of the list which will be modified,
    # and will not affect the array slicing during the loop.
    final_text = list(text)

    # Looping through the list in reverse since we're eliminating
    # the second anagram we find from the original list order.
    count = 0
    for i in range(0, limit):
        if text[i+1:] and checkForAnagrams(text[i], text[i+1:]):
            final_text.pop(i - count)
            count += 1

    return sorted(final_text)

Tôi muốn hiểu trong hàm funwithanagrams, văn bản [i+1:] hữu ích như thế nào?

if checkForAnagrams(text[i], text[i+1:]):

sẽ đạt được đầu ra tương tự.

PS-Đây không phải là mã của tôi. Tôi đã tìm thấy nó trực tuyến và thực sự muốn biết văn bản [i+1:] sẽ tác động đến đầu ra như thế nào?

• Cách tiếp cận 2: sử dụng số nguyên tố để kiểm tra anagram
• Số nguyên tố có một tính chất cơ bản là unique factorization (tạm dịch: tính phân tích duy nhất). Tính chất này phát biểu rằng mọi số lớn hơn 1 đều có thể được viết thành tích của một hoặc nhiều số nguyên tố và tích đó là duy nhất.

This theorem states that every integer larger than 1 can be written as a product of one or more primes. More strongly, this product is unique in the sense that any two prime factorizations of the same number will have the same numbers of copies of the same primes, although their ordering may differ

Chúng ta sẽ sử dụng tính chất này để có thể group các từ là anagram của nhau lại. Cách tiếp cận đó là gắn 26 chữ cái với 26 số nguyên tố bất kỳ. Sau đó chúng ta lặp qua từng từ và tính tích của các số nguyên tố tương ứng với các chữ cái trong từ. Các từ có tích bằng nhau thì là anagram của nhau theo tính chất unique factorization ở trên. Ví dụ:

Lưu ý: từ Python 3.8, math.prod mới được thêm vào

Lời giải của mình cho hướng tiếp cận này là:

Trong bài blog này, mình sẽ đưa ra những cách giải tiêu biểu của bài toán này sử dụng ngôn ngữ Python.

Đề bài

Viết một chương trình nhận một list các từ và trả ra các list gồm các list con gồm các từ, cụm từ anagram của nhau.

Input:

["yo", "act", "flop", "tac", "foo", "cat", "oy", "olfp"]

Output mong muốn:

[
   ["foo"],
   ["flop", "olfp"],
   ["oy", "yo"],
   ["act", "cat", "tac"]
 ]
 

Bài này có khá nhiều cách để giải bài toán này nhưng bài blog này mình chỉ đưa ra 2 cách tiêu biểu và khá tối ưu về mặt space và time complexity.

Cách tiếp cận 1: sort string

Các từ anagram là sử dụng chung một tập chữ cái và có thứ tự sắp xếp khác nhau do đó khi chúng ta sort 1 cặp anagram string trong Python thì sẽ cho ra kết quả giống nhau.

In [1]: sorted('evil') 
Out[1]: ['e', 'i', 'l', 'v'] 
In [2]: ''.join(sorted('evil')) 
Out[2]: 'eilv' 
In [3]: sorted('vile') 
Out[3]: ['e', 'i', 'l', 'v'] 
In [4]: ''.join(sorted('vile')) 
Out[4]: 'eilv'

Do đó cách tiếp cận này sẽ nhóm các từ anagram với nhau sử dụng key là sorted string của nó. Lời giải của mình như sau:

from collections import defaultdict
def groupAnagrams(words):
    result = defaultdict(list)
    for word in words:
        sorted_word = ''.join(sorted(word))
        result[sorted_word].append(word)
    return list(result.values())

Input:

["yo", "act", "flop", "tac", "foo", "cat", "oy", "olfp"]

Output:

[
   ["yo", "oy"],
   ["act", "tac", "cat"],
   ["flop", "olfp"],
   ["foo"]
 ]
 

Phân tích space và time complexity

Chú thích: với w là số lượng từ đầu vào, n là độ dài của từ lớn nhất.

Space complexity là O(wn): do space complexity của mỗi từ là O(n). Do đó, the space complexity của w từ là O(wn).

Time complexity là O(w * nlogn):

• Time complexity lặp qua list words là O(w).
  
• Time complexity mỗi lần sort string là O(n * logn).
  
• Time complexity mỗi lần append phần tử mới vào list là O(1).

Do đó time complexity của lời giải là O(w * n * logn).

Cách tiếp cận 2: sử dụng số nguyên tố để kiểm tra anagram

Số nguyên tố có một tính chất cơ bản là unique factorization (tạm dịch: tính phân tích duy nhất). Tính chất này phát biểu rằng mọi số lớn hơn 1 đều có thể được viết thành tích của một hoặc nhiều số nguyên tố và tích đó là duy nhất.

This theorem states that every integer larger than 1 can be written as a product of one or more primes. More strongly, this product is unique in the sense that any two prime factorizations of the same number will have the same numbers of copies of the same primes, although their ordering may differ

Chúng ta sẽ sử dụng tính chất này để có thể group các từ là anagram của nhau lại. Cách tiếp cận đó là gắn 26 chữ cái với 26 số nguyên tố bất kỳ. Sau đó chúng ta lặp qua từng từ và tính tích của các số nguyên tố tương ứng với các chữ cái trong từ. Các từ có tích bằng nhau thì là anagram của nhau theo tính chất unique factorization ở trên. Ví dụ:

 In [1]: import math
 In [2]: prime_mapping = {'a': 2, 'b': 3, 'c': 5}
 In [3]: math.prod(prime_mapping[c] for c in 'abc')
 Out[3]: 30
 In [4]: math.prod(prime_mapping[c] for c in 'cba')
 Out[4]: 30
     

Lưu ý: từ Python 3.8, math.prod mới được thêm vào

Lời giải của mình cho hướng tiếp cận này là:

import math
import string
from collections import defaultdict
def groupAnagrams(words):
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,
              37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
              79, 83, 89, 97, 101]  # 26 prime numbers
    prime_mapping = dict(zip(string.ascii_lowercase, primes))
    result = defaultdict(list)
    for word in words:
        product = math.prod(prime_mapping[c] for c in word)
        result[product].append(word)
    return list(result.values())

Input:

if checkForAnagrams(text[i], text[i+1:]):

Output:

if checkForAnagrams(text[i], text[i+1:]):

Phân tích space và time complexity

Chú thích: với w là số lượng từ đầu vào, n là độ dài của từ lớn nhất

Space complexity bằng với cách trên, là: O(wn). Time complexity là O(wn). Giải thích:
Time complexity là O(wn). Giải thích:

• Time complexity khi lặp qua list words 1 lần là O(w)
• Time complexity để thực hiện n phép nhân (tương ứng n ký tự của một từ) là O(n) (Giả sử là phép nhân là O(1)).

Do đó time complexity là O(w * n)

Kết luận

Hai cách giải trên chưa phải là tất cả các cách để kiểm tra và group các anagrams nhưng mong rằng bài blog này có thể giúp bạn trên một phương diện nào đó. Nếu bạn thấy bài blog thú vị hãy chia sẻ để nhiều người biết đến hơn nhé Và hãy đón chờ thêm các bài blog của mình về chủ đề Data Structure & Algorithm trên Tech blog của BizFly Cloud nha!