Giả sử chúng ta có hai chuỗi s và t có cùng độ dài. Hãy xem xét một phép toán trong đó chúng ta chọn hai chỉ số trong một chuỗi (không nhất thiết phải khác nhau) và hoán đổi các ký tự tại các chỉ số đã chọn. Chúng tôi phải kiểm tra xem liệu có thể làm cho cả hai chuỗi giống nhau bằng cách thực hiện nhiều nhất một chuỗi hoán đổi trên chính xác một trong các chuỗi hay không.
Vì vậy, nếu đầu vào giống như s ="hello" t ="hlelo", thì đầu ra sẽ là True vì chúng ta cần hoán đổi 'e' và 'l' thành s hoặc t để chúng bằng nhau.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
max_diffs:=2
-
khác:=0
-
st:=một tập hợp mới
-
st2:=một tập hợp mới
-
đối với tôi trong phạm vi từ 0 đến kích thước của s, thực hiện
-
nếu s [i] không giống với t [i] thì
-
diffs:=diffs + 1
-
-
nếu s [i] không có trong st, thì
-
chèn s [i] vào st
-
-
nếu t [i] không có trong st2, thì
-
chèn t [i] vào st2
-
-
nếu diffs> max_diffs thì
-
trả về Sai
-
-
-
trả về true nếu (diffs giống 0 hoặc diffs giống 2) và kích thước của st giống với kích thước của st2 và st giống với st2, nếu không thì false
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
def solve(s, t): max_diffs=2 diffs=0 st = set() st2 = set() for i in range(len(s)): if s[i] != t[i]: diffs+=1 if s[i] not in st: st.add(s[i]) if t[i] not in st2: st2.add(t[i]) if diffs > max_diffs: return False return (diffs == 0 or diffs == 2) and len(st) == len(st2) and st == st2 s = "hello" t = "hlelo" print(solve(s, t))
Đầu vào
"hello", "hlelo"
Đầu ra
True