단어 목록과 문자라는 문자열이 있다고 가정하고 주어진 문자를 재배열하여 만들 수 있는 가장 긴 단어의 크기를 찾아야 합니다. 문자에 별표 문자(*)가 있을 수 있으며 모든 문자와 일치할 수 있습니다. 그리고 모든 문자를 사용할 필요는 없습니다.
따라서 입력이 단어 =["prince", "rice", "price", "limit", "hello"] letters ="*r**ce*"인 경우 출력은 6이 됩니다. 우리가 만들 수 있는 가장 긴 단어는 "prince" 길이가 6입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- has :=문자로 된 각 요소의 문자와 빈도를 포함하는 지도
- valid() 함수를 정의합니다. 시간이 걸립니다
- need :=s에 있는 각 요소의 문자와 빈도를 포함하는 지도
- extra :=모든 요소의 합(최대 0 및 필요[char] - 필요한 모든 문자에 대한 has[char])
- 추가 <=가["*"]인 경우 true를 반환
- 기본 방법에서 다음을 수행합니다.
- 목록에 있는 모든 요소의 최대값 반환 [단어가 유효한 경우 단어의 모든 단어에 대한 단어 크기]
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시
from collections import Counter class Solution: def solve(self, words, letters): has = Counter(letters) def valid(s): need = Counter(s) extra = sum([max(0, need[char] - has[char]) for char in need]) return extra <= has["*"] return max([len(word) for word in words if valid(word)]) ob = Solution() words = ["prince", "rice", "price", "limit", "hello"] letters = "*r**ce*" print(ob.solve(words, letters))
입력
["prince", "rice", "price", "limit", "hello"], "*r**ce*"
출력
6