পাইথনে দুটি স্ট্রিং সমান করতে প্রয়োজনীয় ন্যূনতম সংখ্যক প্রিপ্রসেস চালনা খুঁজুন

ধরুন আমাদের কাছে শুধুমাত্র ছোট হাতের অক্ষর সহ একই দৈর্ঘ্যের দুটি স্ট্রিং P এবং Q আছে, নীচের ক্রিয়াকলাপগুলি প্রয়োগ করার পরে স্ট্রিং Q এর সমান করার জন্য আমাদের স্ট্রিং P-এ ন্যূনতম সংখ্যক প্রাক-প্রসেসিং পদক্ষেপগুলি গণনা করতে হবে -

যেকোনো সূচক 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) এবং swap(P1, P5)৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=P
এর আকার
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
- সাইজ :=আমার_ম্যাপের আকার
- যদি আকার 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"