Hai hướng giải bài toán Anagram bằng Python
Anagram - phép đảo chữ
Bạn có thể thấy ở trên: banner của bài là 1 GIF thể hiện 1 cụm từ "supersonic" và "percussion". Hai từ này dùng chung một tập chữ cái và chỉ cần sắp xếp lại là có một từ mới. Những từ như này được gọi là "anagram" (phép đảo chữ). Vậy anagram chính xác là gì ? Theo Wikipedia, anagram là một từ hoặc cụm từ được tạo thành bởi việc sắp xếp lại một từ hay một cụm từ khác. Các ví dụ về anagram như: "New York Times" ⇒ "monkeys write" hay "evil" ⇒ "vile".
An anagram is a word or phrase formed by rearranging the letters of a different word or phrase
"Xác định hai từ có phải anagram của nhau hay không" là một câu đố tuy đơn giản nhưng kinh điển trong Computer Science và thường được sử dụng như câu hỏi "dạo đầu" khi phỏng vấn các ứng viên.
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:
["cinema", "a", "flop", "iceman", "meacyne", "lofp", "olfp"]
Output:
[
["cinema", "iceman"],
["a"],
["flop", "lofp", "olfp"],
["meacyne"]
]
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 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!
