สมมติว่าเรามีสองสตริง s และ t เราต้องตรวจสอบว่า s และ t อยู่ใกล้หรือไม่ เราสามารถพูดได้ว่าสายอักขระสองเส้นอยู่ใกล้กันถ้าเราสามารถบรรลุหนึ่งจากอีกสายหนึ่งโดยใช้การดำเนินการต่อไปนี้ -
-
แลกเปลี่ยนอักขระสองตัวที่มีอยู่ (เหมือน abcde ถึง aecdb)
-
เปลี่ยนทุกการเกิดขึ้นของตัวละครที่มีอยู่เป็นตัวละครอื่นที่มีอยู่ และทำเช่นเดียวกันกับตัวละครอื่นๆ ด้วย (เช่น aacabb -> bbcbaa (ในที่นี้ a ทั้งหมดจะถูกแปลงเป็น b และในทางกลับกัน))
เราสามารถใช้การดำเนินการกับสตริงใดก็ได้กี่ครั้งก็ได้ตามต้องการ
ดังนั้น หากอินพุตเป็น s ="zxyyyx", t ="xyyzzz" ผลลัพธ์จะเป็นจริง เพราะเราสามารถรับ t จาก s ได้ใน 3 การดำเนินการ ("zxyyyx" -> "zxxyyy"), ("zxxyyy" -> "yxxzzz") และ ("yxxzzz" -> "xyyzzz")
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ถ้า s และ t มีอักขระพิเศษใด ๆ แล้ว
-
คืนค่าเท็จ
-
-
a :=รายการค่าความถี่ทั้งหมดของอักขระใน s
-
b :=รายการค่าความถี่ทั้งหมดของอักขระใน t
-
เรียงลำดับรายการ
-
เรียงลำดับรายการ b
-
ถ้า a ไม่เหมือนกับ b แล้ว
-
คืนค่าเท็จ
-
-
คืนค่า True
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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)) อินพุต
"zxyyyx", "xyyzzz"
ผลลัพธ์
True
