파이썬에서 연결이 대상과 동일한 하위 시퀀스의 최소 수를 찾는 프로그램

소스와 타겟이라는 두 개의 문자열이 있다고 가정하고 연결하면 타겟과 동일하도록 구성할 수 있는 소스의 하위 시퀀스의 최소 수를 찾아야 합니다. 해당 결과가 없으면 -1을 반환합니다.

따라서 입력이 source ="xyz" target ="xyzyzz"와 같으면 출력은 ["xyz" + "yz" + "z"]

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

• s_size :=s의 크기, t_size :=t의 크기
• concat_count :=0, target_idx :=0
• target_idx
• source_idx :=0
• temp_index :=target_idx
• source_idx
• s[source_idx]가 t[target_idx]와 같으면
  • target_idx :=target_idx + 1
• source_idx :=source_idx + 1

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

예시

class Solution:
   def solve(self, s, t):
      s_size, t_size = len(s), len(t)
      concat_count = 0
      target_idx = 0
      while target_idx < t_size:
         source_idx = 0
         temp_index = target_idx

         while source_idx < s_size and target_idx < t_size:
            if s[source_idx] == t[target_idx]:
               target_idx += 1
            source_idx += 1

         if temp_index == target_idx:
            return -1
         concat_count += 1
      return concat_count
ob = Solution()
source = "xyz"
target = "xyzyzz"
print(ob.solve(source, target))

입력

"xyz", "xyzyzz"

출력

3