Python을 사용하여 가장 긴 회문 부분 수열의 길이를 찾는 프로그램

<시간/>

문자열이 주어졌다고 가정해 봅시다. 우리는 길이가 짝수이고 중간을 제외하고 두 개의 연속적인 동일한 문자를 포함하지 않는 회문 부분 수열을 찾아야 합니다. 이 유형의 부분 문자열의 길이를 출력으로 반환해야 합니다.

따라서 입력이 s ='effeffe'와 같으면 출력은 4가 됩니다.

길이가 짝수인 회문 부분수열이 하나만 있기 때문에 출력은 4입니다. 문자열은 길이가 4인 'eff'입니다.

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

n :=s
의 크기
dp :=one n x n 2d 배열에서 각 항목은 (0, 공백 문자열) 형식의 쌍입니다.
n-1 ~ -1 범위의 i에 대해 1 감소, 수행
- i+1에서 n 사이의 j에 대해 수행
  - s[i]가 s[j]와 같고 dp[i+1, j-1]의 문자열이 s[i]가 아니면
    - dp[i, j] :=쌍 만들기 (dp[i+1, j-1] + 2, s[i]의 첫 번째 요소)
  - 그렇지 않으면
    - dp[i, j] :=쌍의 첫 번째 요소가 최대인 (dp[i+1, j], dp[i, j-1], dp[i+1,j-1]) 중에서 선택
  - dp[0, n-1]
    에 저장된 쌍의 첫 번째 요소를 반환합니다.

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

예시

def solve(s):
   n = len(s)
   dp = [[(0, '')]*n for _ in range(n)]
   for i in range(n-1, -1, -1):
      for j in range(i+1, n):
         if s[i]== s[j] and dp[i+1][j-1][1] != s[i]:
            dp[i][j] = (dp[i+1][j-1][0] + 2, s[i])
         else:
            dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], key=lambda x: x[0])
   return dp[0][n-1][0]
print(solve('efeffe'))

입력

'efeffe'