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"인 경우 출력은 P0 ='q', P2 ='r', P3 ='p' 및 P4 ='로 설정한 것처럼 4가 됩니다. q' 및 P는 "qqrpqqp"가 됩니다. 그 후 다음과 같은 일련의 작업으로 동일한 문자열을 얻을 수 있습니다. swap(P1, Q1) 및 swap(P1, P5).

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=P의 크기
해상도 :=0
0에서 n / 2 범위의 i에 대해 수행
- 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
- 크기 :=my_map의 크기
- 크기가 4와 같으면
  - res :=res + 2
- 그렇지 않으면 크기가 3과 같을 때
  - res :=res + 1 + (P[i]가 P[n - i - 1]과 같을 때 1, 그렇지 않으면 0)
- 그렇지 않으면 크기가 2와 같을 때
  - res :=res + my_map[P[i]]는 2와 동일하지 않습니다.
n mod 2가 1과 같고 P[n/2]가 Q[n/2]와 같지 않으면
- 해상도 :=해상도 + 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"