Phân tích python

You could see on on. biểu ngữ của bài là 1 GIF có thể hiển thị 1 cụm từ "siêu âm" và "bộ gõ". Hai từ này dùng chung một chữ cái và chỉ cần sắp xếp lại là có một từ mới. Những từ như thế này được gọi là "đảo chữ cái" [phép đảo chữ]. Do đó đảo chữ chính xác là gì ? . Các ví dụ về anagram as. "New York Times" ⇒ "khỉ viết" hay "xấu xa" ⇒ "thấp hèn"

Đảo chữ là một từ hoặc cụm từ được hình thành bằng cách sắp xếp lại các chữ cái của một từ hoặc cụm từ khác

"Xác định hai từ phải đảo chữ của nhau hay không" là một câu đố tuy đơn giản nhưng kinh điển trong Khoa học Máy tính và thường được sử dụng như câu hỏi "dạo đầu" khi phỏng vấn các thành viên ứng dụng

Trong bài blog này, mình sẽ đưa ra 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 danh sách các từ và trả ra các danh sách bao gồm các danh sách con bao gồm các từ, cụm từ đảo chữ của nhau

Đầu vào

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

Đầu ra 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ề độ phức tạp của mặt không gian và thời gian

Cách tiếp cận 1. sắp xếp chuỗi

Các từ đảo chữ 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 sắp xếp 1 cặp chuỗi đảo chữ 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ừ đảo ngữ với nhau sử dụng khóa là chuỗi được sắp xếp của nó. Lời giải thích 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[]]

Đầu vào

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

đầu ra

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

Phân tích độ phức tạp không gian và thời gian

Chú thích. with w is the number of start in, n is the length of the best

Độ phức tạp không gian là O[wn]. độ phức tạp không gian của mỗi từ là O[n]. Do đó, độ phức tạp không gian của w từ là O[wn]

Độ phức tạp thời gian là O[w * nlogn]

• Độ phức tạp thời gian thông qua danh sách từ là O[w]
  
• Độ phức tạp thời gian mỗi lần sắp xếp chuỗi là O[n * logn]
  
• Độ phức tạp thời gian mỗi lần thêm phần tử mới vào danh sách là O[1]

Độ phức tạp thời gian 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 đảo chữ

Số nguyên tố có một tính chất cơ bản là thừa số duy nhất [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 nguyên tố và tích đó là duy nhất

Định lý này phát biểu rằng mọi số nguyên lớn hơn 1 đều có thể viết dưới dạng tích của một hoặc nhiều số nguyên tố. Mạnh mẽ hơn, tích này là duy nhất theo nghĩa là bất kỳ hai phép phân tích thành thừa số nguyên tố nào của cùng một số sẽ có cùng số bản sao của các số nguyên tố giống nhau, mặc dù thứ tự của chúng có thể khác nhau

Chúng ta sẽ sử dụng tính chất này để có thể nhóm các từ đảo ngữ của nhau lại. Cách tiếp cận đó là gắn 26 chữ cái với 26 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ó giá trị bằng nhau thì là đảo ngữ của nhau theo tính chất duy nhất thừa số ở 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, toán. sản phẩm mới được thêm vào

Lời giải thích 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[]]

Đầu vào

đầu ra

[
   ["cinema", "iceman"],
   ["a"],
   ["flop", "lofp", "olfp"],
   ["meacyne"]
 ]
 

Phân tích độ phức tạp không gian và thời gian

Chú thích. with w is the number of start in, n is the length of the best

Độ phức tạp của không gian bằng với cách trên, là. Riêng].
Độ phức tạp thời gian là O[wn]. Giải thích.

• Độ phức tạp thời gian khi lặp qua danh sách từ 1 lần là O[w]
• Độ phức tạp về thời gian để thực hiện phép nhân [tương ứng với ký tự của một từ] là O[n] [Giả sử được phép nhân là O[1]]

Do đó độ phức tạp thời gian là O[w * n]

Kết luận

Hai cách giải trên không phải là tất cả các cách để kiểm tra và nhóm đảo chữ cái 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 on Tech blog của BizFly Cloud nha