Computer >> Máy Tính >  >> Lập trình >> Python

Tìm số lần di chuyển tiền xử lý tối thiểu cần thiết để tạo hai chuỗi bằng nhau trong Python

Giả sử chúng ta có hai chuỗi P và Q có cùng độ dài chỉ có chữ thường, chúng ta phải đếm số lần xử lý trước tối thiểu trên chuỗi P cần thiết để làm cho nó bằng với chuỗi Q sau khi áp dụng các phép toán dưới đây -

  • Chọn bất kỳ chỉ mục i nào và hoán đổi các ký tự pi và qi.

  • Chọn bất kỳ chỉ mục i nào và hoán đổi các ký tự pi và pn - i - 1.

  • Chọn bất kỳ chỉ mục i nào và hoán đổi các ký tự qi và qn - i - 1.

Lưu ý - Giá trị của i trong phạm vi (0 ≤ i

Trong một lần di chuyển, chúng ta có thể thay đổi một ký tự trong P bằng bất kỳ ký tự nào khác trong bảng chữ cái tiếng Anh.

Vì vậy, nếu đầu vào giống như P =“pqprpqp”, Q =“qprpqpp”, thì đầu ra sẽ là 4 như thể chúng ta đặt P0 ='q', P2 ='r', P3 ='p' và P4 =' q 'và P sẽ là "qqrpqqp". Sau đó, chúng ta có thể nhận được các chuỗi bằng nhau bằng chuỗi hoạt động sau:hoán đổi (P1, Q1) và hoán đổi (P1, P5).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • n:=kích thước của P

  • res:=0

  • đối với tôi trong phạm vi từ 0 đến n / 2, hãy thực hiện

    • my_map:=một bản đồ mới

    • my_map [P [i]]:=1

    • nếu P [i] giống P [n - i - 1] thì

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

    • nếu Q [i] nằm trong my_map, thì

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

    • nếu không,

      • my_map [Q [i]]:=1

    • nếu Q [n - i - 1] nằm trong my_map, thì

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

    • nếu không,

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

    • size:=kích thước của my_map

    • nếu kích thước bằng 4 thì

      • res:=res + 2

    • ngược lại khi kích thước bằng 3 thì

      • res:=res + 1 + (1 khi (P [i] giống P [n - i - 1]), nếu không thì 0)

    • ngược lại khi kích thước bằng 2 thì

      • res:=res + my_map [P [i]] không giống với 2

  • nếu n mod 2 giống 1 và P [n / 2] không giống Q [n / 2] thì

    • res:=res + 1

  • trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

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))

Đầu vào 

"pqprpqp", "qprpqpp"

Đầu ra 

4