두 개의 문자열 s1과 s2가 있다고 가정합니다. s1과 s2의 특별한 부분 문자열인 가장 긴 문자열 s3의 크기를 찾아야 합니다.
y에서 0개 이상의 문자를 제거하여 x를 생성할 수 있는 경우 문자열 x는 다른 문자열 y의 특수 부분 문자열이라고 말할 수 있습니다.
따라서 입력이 s1 ='pineapple' s2 ='people'과 같으면 특수 부분 문자열이 'peple'이고 크기가 5이므로 출력은 5가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- prev :=일부 키가 없으면 0을 반환하는 새 사전
- 0에서 s1 - 1의 크기 범위에 있는 i에 대해
- cur :=일부 키가 없으면 0을 반환하는 새 사전
- 0에서 s2-1의 크기 범위에 있는 j에 대해
- cur[j] :=prev[j - 1] + 1(s1[i]이 s2[j]일 때), 그렇지 않으면 cur[j -1] 및 prev[j]의 최대값
- 이전 :=cur
- 이전 반환[s2 -1의 크기]
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import defaultdict def solve(s1, s2): prev = defaultdict(int) for i in range(len(s1)): cur = defaultdict(int) for j in range(len(s2)): cur[j] = prev[j - 1] + 1 if s1[i] == s2[j] else max(cur[j - 1], prev[j]) prev = cur return prev[len(s2)-1] s1 = 'pineapple' s2 = 'people' print(solve(s1, s2))
입력
'pineapple', 'people'
출력
5