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 defaultdictdef 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:]]:
0Output:
if checkForAnagrams[text[i], text[i+1:]]:
1Phâ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!