ค้นหาจำนวนขั้นต่ำของการย้ายกระบวนการล่วงหน้าที่จำเป็นในการทำให้สองสตริงเท่ากันในPython

สมมติว่าเรามีสองสตริง P และ Q ที่มีความยาวเท่ากันโดยมีตัวพิมพ์เล็กเท่านั้น เราต้องนับจำนวนขั้นต่ำของการย้ายการประมวลผลล่วงหน้าในสตริง P เพื่อให้เท่ากับสตริง Q หลังจากใช้การดำเนินการด้านล่าง -

• เลือกดัชนี i และสลับอักขระ pi และ qi

• เลือกดัชนี i และสลับอักขระ pi และ pn – i – 1.

• เลือกดัชนี i และสลับอักขระ qi และ qn – i – 1.

หมายเหตุ − ค่าของ i อยู่ในช่วง (0 ≤ i

ในคราวเดียว เราสามารถเปลี่ยนอักขระใน P ด้วยอักขระอื่นๆ ของตัวอักษรภาษาอังกฤษได้

ดังนั้น หากอินพุตเป็น P =“pqprpqp”, Q =“qprpqpp” เอาต์พุตจะเป็น 4 เหมือนกับว่าเราตั้งค่า P0 ='q', P2 ='r', P3 ='p' และ P4 =' q' และ P จะเป็น “qqrpqqp” หลังจากนั้น เราจะได้สตริงที่เท่ากันตามลำดับการดำเนินการต่อไปนี้:swap(P1, Q1) and swap(P1, P5)

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของพี

• res :=0

• สำหรับฉันอยู่ในช่วง 0 ถึง n / 2 ทำ

  • my_map :=แผนที่ใหม่

  • my_map[P[i]] :=1

  • ถ้า P[i] เหมือนกับ P[n - i - 1] แล้ว

    • my_map[P[n - i - 1]] :=my_map[P[n - i - 1]] + 1

  • ถ้า Q[i] อยู่ใน my_map แล้ว

    • my_map[Q[i]] :=my_map[Q[i]] + 1

  • มิฉะนั้น

    • my_map[Q[i]] :=1

  • ถ้า Q[n - i - 1] อยู่ใน my_map แล้ว

    • my_map[Q[n - 1 - i]] :=my_map[Q[n - 1 - i]] + 1

  • มิฉะนั้น

    • my_map[Q[n - 1 - i]] :=1

  • size :=ขนาดของ my_map

  • ถ้าขนาดเท่ากับ 4 แล้ว

    • res :=res + 2

  • มิฉะนั้นเมื่อขนาดเท่ากับ 3 แล้ว

    • res :=res + 1 + (1 เมื่อ (P[i] เหมือนกับ P[n - i - 1]) มิฉะนั้น 0)

  • มิฉะนั้นเมื่อขนาดเท่ากับ 2 แล้ว

    • res :=res + my_map[P[i]] ไม่เหมือนกับ 2

• ถ้า n mod 2 เหมือนกับ 1 และ P[n / 2] ไม่เหมือนกับ Q[n / 2] แล้ว

  • res :=res + 1

• ผลตอบแทน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def count_preprocess(P, Q):
   n = len(P)
   res = 0
   for i in range(n // 2):
      my_map = dict()
      my_map[P[i]] = 1
      if P[i] == P[n - i - 1]:
         my_map[P[n - i - 1]] += 1
      if Q[i] in my_map:
         my_map[Q[i]] += 1
      else:
         my_map[Q[i]] = 1
      if Q[n - i - 1] in my_map:
         my_map[Q[n - 1 - i]] += 1
      else:
         my_map[Q[n - 1 - i]] = 1
      size = len(my_map)
      if (size == 4):
         res += 2
      elif (size == 3):
         res += 1 + (P[i] == P[n - i - 1])
      elif (size == 2):
         res += my_map[P[i]] != 2
   if (n % 2 == 1 and P[n // 2] != Q[n // 2]):
      res += 1
   return res

A = "pqprpqp"
B = "qprpqpp"
print(count_preprocess(A, B))

อินพุต

"pqprpqp", "qprpqpp"

ผลลัพธ์

4