Giả sử chúng ta có hai chuỗi s và t, chúng ta phải kiểm tra xem s và t có gần nhau hay không. Chúng ta có thể nói hai chuỗi gần nhau nếu chúng ta có thể đạt được một từ chuỗi kia bằng cách sử dụng các thao tác sau -
-
Trao đổi bất kỳ hai ký tự hiện có. (như abcde thành aecdb)
-
Thay đổi mọi lần xuất hiện của một ký tự hiện có thành một ký tự hiện có khác và thực hiện tương tự với các ký tự khác. (như aacabb -> bbcbaa (ở đây tất cả a được chuyển đổi thành b và ngược lại))
Chúng ta có thể sử dụng các thao tác trên một trong hai chuỗi bao nhiêu lần tùy ý.
Vì vậy, nếu đầu vào là s ="zxyyyx", t ="xyyzzz", thì đầu ra sẽ là true, vì chúng ta có thể lấy t từ s trong 3 phép toán. ("zxyyyx" -> "zxxyyy"), ("zxxyyy" -> "yxxzzz") và ("yxxzzz" -> "xyyzzz").
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
nếu s và t có bất kỳ ký tự không phổ biến nào thì
-
trả về Sai
-
-
a:=danh sách tất cả các giá trị tần suất của các ký tự trong s
-
b:=danh sách tất cả các giá trị tần số của các ký tự trong t
-
sắp xếp danh sách một
-
sắp xếp danh sách b
-
nếu a không giống b thì
-
trả về Sai
-
-
trả về True
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
from collections import Counter
def solve(s, t):
if set(s) != set(t):
return False
a = list(Counter(s).values())
b = list(Counter(t).values())
a.sort()
b.sort()
if a != b:
return False
return True
s = "zxyyyx"
t = "xyyzzz"
print(solve(s, t)) Đầu vào
"zxyyyx", "xyyzzz"
Đầu ra
True