파이썬에서 가장 짧은 수퍼 시퀀스의 길이를 찾는 프로그램

<시간/>

두 개의 문자열 s와 t가 있다고 가정합니다. s와 t를 모두 부분 시퀀스로 포함하는 가장 짧은 문자열의 길이를 찾아야 합니다.

따라서 입력이 s ="pipe" t ="people"과 같으면 가능한 상위 시퀀스 중 하나가 "pieople"이므로 출력은 7이 됩니다.

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

m :=s의 크기, n :=t의 크기
table :=크기가 (n + 1) x (m + 1)이고 0으로 채워진 테이블
0에서 m 사이의 i에 대해 수행
- 0에서 n 사이의 j에 대해 수행
  - i가 0과 같거나 j가 0과 같으면
    - 테이블[i, j] :=0
  - 그렇지 않으면
    - s[i - 1]이 t[j - 1]과 같으면
      - 테이블[i, j] :=1 + 테이블[i - 1, j - 1]
    - 그렇지 않으면
      - table[i, j] =table[i, j - 1] 및 table[i - 1, j]
        의 최대값
m + n 반환 - 테이블[m, n]

예시

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

class Solution:
   def solve(self, s, t):
      m = len(s)
      n = len(t)
      table = [[0 for i in range(n + 1)] for j in range(m + 1)]
      for i in range(m + 1):
         for j in range(n + 1):
            if i == 0 or j == 0:
               table[i][j] = 0
            else:
               if s[i - 1] == t[j - 1]:
                  table[i][j] = 1 + table[i - 1][j - 1]
            else:
               table[i][j] = max(table[i][j - 1], table[i - 1][j])
      return m + n - table[m][n]
ob = Solution()
s = "pipe"
t = "people"
print(ob.solve(s, t))

입력

"pipe", "people"