Python에서 첫 번째 또는 마지막에서 제거하고 다시 삽입하여 대상을 만드는 프로그램

<시간/>

두 개의 문자열 S와 T가 있고 서로 순열이라고 가정합니다. S의 첫 번째 또는 마지막 문자를 제거하고 문자열의 아무 곳에나 삽입하는 작업이 있다고 가정합니다. 그런 다음 S를 T로 변환하는 데 필요한 최소 연산 수를 찾으십시오.

따라서 입력이 s ="zyvxw" t ="vwxyz"와 같으면 다음 작업과 같이 출력은 3이 됩니다. "w"를 제거하고 "v" 뒤에 삽입하여 "zyvwx"를 얻습니다. "z" 제거 "x" 뒤에 삽입하여 "yvwxz"를 얻습니다. "y"를 제거하고 "x" 뒤에 삽입하여 "vwxyz"를 얻습니다.

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

ans :=s의 크기, n :=s의 크기
0에서 n-1 사이의 i에 대해 수행
- k :=0
- 범위 i에서 n-1까지의 j에 대해 수행
  - k 범위에서 t 크기까지의 k에 대해 수행
    - s[j]가 t[k]와 같으면
      - ans :=ans 및 n의 최소값 - (j - i + 1)
      - 루프에서 나오다
  - k :=k + 1
- 반환

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

예

class Solution:
   def solve(self, s, t):
      ans = n = len(s)

      for i in range(n):
         k = 0
         for j in range(i, n):
            for k in range(k, len(t)):
               if s[j] == t[k]:
                  ans = min(ans, n - (j - i + 1))
                  break
            k += 1

      return ans

ob = Solution()
s = "zyvxw"
t = "vwxyz"
print(ob.solve(s, t))

입력

"zyvxw", "vwxyz"