Python에서 문자열을 문자열로 만들기 위해 최소 삭제를 찾는 프로그램

<시간/>

두 개의 소문자 문자열 s와 t가 있다고 가정하고 이제 이 두 문자열에서 문자를 삭제할 수 있는 작업을 고려합니다. s와 t를 같게 만드는 데 필요한 최소 연산 수를 찾아야 합니다.

따라서 입력이 s ="pipe" t ="ripe"와 같으면 출력은 2가 됩니다. s에서 "p"를 삭제하고 t에서 "r"을 삭제하여 이러한 문자열을 동일한 "ipe"로 만들 수 있기 때문입니다

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

m :=s의 크기
n :=t의 크기
dp() 함수를 정의합니다. i, j
i가 m과 같으면
- n - j를 반환
그렇지 않으면 j가 n과 같을 때
- m - i를 반환
그렇지 않으면
- s[i]가 t[j]와 같으면
  - dp(i + 1, j + 1)를 반환
- 그렇지 않으면
  - 반환 1 + (dp(i + 1, j) 및 dp(i, j + 1)의 최소값)
메인 메소드에서 dp(0, 0)을 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(s, t):
   m = len(s)
   n = len(t)

   def dp(i, j):
      if i == m:
         return n - j
      elif j == n:
         return m - i
      else:
         if s[i] == t[j]:
            return dp(i + 1, j + 1)
         else:
            return 1 + min(dp(i + 1, j), dp(i, j + 1))
   return dp(0, 0)

s = "pipe"
t = "ripe"
print(solve(s, t))

입력

"pipe", "ripe"