Hai hướng giải bài toán Anagram bằng Python

966
22-09-2021
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!

SHARE
Hỗ trợ kỹ thuật
Kinh doanh, CSKH