소문자 문자열이 포함된 w라는 단어 목록이 있다고 가정합니다. 각 이전 단어가 다음 단어의 접두어이고 다음 단어에 하나의 새 문자가 추가되는 가장 긴 w 시퀀스의 길이를 찾아야 합니다.
따라서 입력이 w =["pqr", "pq", "m", "mn", "pqrs"]와 같으면 시퀀스를 얻을 수 있기 때문에 출력은 3이 됩니다. ["pq", " pqr", "pqrs"], 길이가 3입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 목록 정렬
- dp :=키의 기본값이 0인 맵
- res :=0
- w의 각 단어에 대해 do
- dp[단어] :=dp[마지막 두 번째 요소까지 단어의 부분 문자열] + 1
- res :=res 및 dp[단어]의 최대값
- 반환 결과
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import defaultdict def solve(w): w.sort() dp = defaultdict(int) res = 0 for word in w: dp[word] = dp[word[:-1]] + 1 res = max(res, dp[word]) return res w = ["pqr", "pq", "m", "mn", "pqrs"] print(solve(w))
입력
["pqr", "pq", "m", "mn", "pqrs"]
출력
3