Trong hướng dẫn này, chúng ta sẽ viết một chương trình nhóm tất cả các từ đảo ngữ trong một danh sách. Trước tiên, hãy xem đảo ngữ là gì .
Bất kỳ hai chuỗi nào có cùng một ký tự theo một thứ tự khác nhau được gọi là đảo ngữ.
Trước khi đi sâu vào giải pháp, hãy xem một ví dụ.
Đầu vào
['cat', 'dog', 'fired', 'god', 'pat', 'tap', 'fried', 'tac']
Đầu ra
[['cat', 'tac'], ['dog', 'god'], ['fried', 'fired'], ['pat', 'tap']]
Chúng tôi sẽ chia vấn đề thành hai phần. Đầu tiên, chúng ta sẽ viết một hàm kiểm tra hai chuỗi có phải là đảo ngữ hay không. Làm theo các bước dưới đây để viết mã kiểm tra đảo ngữ.
- Khởi tạo các chuỗi.
- Sắp xếp cả hai chuỗi.
- Nếu cả hai chuỗi được sắp xếp bằng nhau thì trả về True else Sai .
Ví dụ
# simple lambda function to check whether two strings are anagrams or not
are_anagrams = lambda x, y: str(sorted(x.lower())) == str(sorted(y.lower()))
# calling the function
print(are_anagrams('cat', 'tac'))
print(are_anagrams('cat', 'Tac'))
print(are_anagrams('cat', 'dog')) Đầu ra
Nếu bạn chạy đoạn mã trên, bạn sẽ nhận được kết quả sau.
True True False
Bây giờ, chúng ta biết cách kiểm tra hai chuỗi xem chúng có phải là chữ đảo ngữ hay không. Nhưng, điều đó vẫn chưa đủ để giải quyết vấn đề của chúng ta. Chúng ta cần nhóm (lưu trữ) tất cả các từ đảo ngữ từ một danh sách dưới dạng danh sách con.
Làm thế nào chúng ta có thể giải quyết vấn đề?
Cách tốt nhất là sử dụng từ điển để nhóm các yếu tố. Chúng tôi sẽ có một khóa duy nhất cho các phép đảo chữ liên quan. Sẽ hơi khó hiểu nếu bạn chưa quen với Python. Hãy xem các bước để đạt được những gì chúng ta muốn.
- Khởi tạo danh sách các chuỗi.
- Khởi tạo một từ điển trống.
- Lặp lại danh sách.
- Sắp xếp chuỗi.
- Kiểm tra xem nó có trong từ điển hay không.
-
- Nếu nó xuất hiện trong từ điển, thì hãy nối chuỗi vào danh sách của nó.
- Khác khởi tạo khóa bằng danh sách bao gồm chuỗi hiện tại để lưu trữ các ký tự đảo ngữ.
- In tất cả các giá trị của từ điển trong một danh sách.
Ví dụ
# initialzing a list of strings
anagrams = ['cat', 'dog', 'fired', 'god', 'pat', 'tap', 'fried', 'tac']
# initializing an empty dict
grouped_anagrams = {}
# iterating over the list to group all anagrams
for string in anagrams:
# sorting the string
sorted_string = str(sorted(string))
# checking the string in dict
if sorted_string in grouped_anagrams:
# adding the string to the group anagrams
grouped_anagrams[sorted_string].append(string)
else:
# initializing a list with current string
grouped_anagrams[sorted_string] = [string]
# printing the values of the dict (anagram groups)
print(list(grouped_anagrams.values())) Đầu ra
Nếu bạn chạy đoạn mã trên, bạn sẽ nhận được kết quả sau.
[['dog', 'god'], ['pat', 'tap'], ['cat', 'tac'], ['fired', 'fried']]
Kết luận
Bạn cũng có thể giải quyết vấn đề bằng các cách tiếp cận khác nhau. Có một cấu trúc dữ liệu được gọi là defaultdict điều đó giúp bạn tránh kiểm tra khóa trong từ điển. Bạn có thể khám phá nó và thay đổi mã cho phù hợp.
Nếu bạn có bất kỳ nghi ngờ nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.