สมมติว่าเรามีสองสตริง s และ t เราต้องตรวจสอบว่า s สามารถแปลงเป็น t ใน k ย้ายหรือน้อยกว่าได้หรือไม่ ในการย้ายคุณสามารถดำเนินการเหล่านี้ได้
-
เลือกดัชนี j (เริ่มจาก 1) ใน s โดยที่ 1 <=j <=ขนาดของ s และ j ไม่ถูกเลือกในการเคลื่อนไหวครั้งก่อน และเปลี่ยนอักขระที่ดัชนีนั้น i จำนวนครั้ง
-
อยู่อย่างที่เป็นอยู่
การเปลี่ยนอักขระในที่นี้หมายถึงการแทนที่ด้วยตัวอักษรถัดไปในตัวอักษร (หากตัวอักษรคือ 'z' ให้ตัดเป็น 'a') ดังนั้นการขยับอักขระทีละ i แสดงว่าใช้การดำเนินการกะ i ครั้ง
ดังนั้น หากอินพุตเป็น s ="poput" t ="vwput" k =9 เอาต์พุตจะเป็น True เพราะที่ i =6 เราสามารถแปลง 'p' เป็น 'v' และที่ i =8 เราสามารถแปลง 'o' เป็น 'w' ได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
ถ้าขนาดของ s ไม่เหมือนกับขนาดของ t แล้ว
-
คืนค่าเท็จ
-
-
count :=การถืออาร์เรย์ (ขั้นต่ำ 1 และ (k - i + 1 +(k - i)/26)) สำหรับ i ทั้งหมดตั้งแต่ 0 ถึง 25
-
สำหรับแต่ละอักขระ c1 จาก s และ c2 จาก t ทำ
-
ถ้า c1 ไม่เหมือนกับ c2 แล้ว
-
diff :=(ASCII ของ c2 - ASCII ของ c1 + 26) mod 26
-
ถ้า count[diff] <=0 แล้ว
-
คืนค่าเท็จ
-
-
นับ[diff] :=นับ[diff] - 1
-
-
-
คืนค่า True
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
ตัวอย่าง
def solve(s, t, k): if len(s) != len(t): return False count = [min(1, k - i + 1) + (k - i)//26 for i in range(26)] for c1, c2 in zip(s, t): if (c1 != c2): diff = (ord(c2) - ord(c1) + 26) % 26 if count[diff] <= 0: return False count[diff] -= 1 return True s = "poput" t = "vwput" k = 9 print(solve(s, t,k))
อินพุต
"poput","vwput",9
ผลลัพธ์
True
