문자열 단어 목록이 있다고 가정합니다. 각 문자가 고유하도록 단어의 하위 시퀀스를 연결하여 구성된 문자열을 만들어야 합니다. 우리는 마침내 그러한 가장 긴 연결의 길이를 찾아야 합니다.
따라서 입력이 단어 =["xyz", "xyw", "wab", "cde"]와 같으면 중복 문자가 포함되어 있으므로 단어를 선택할 수 없으므로 출력은 9가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
답변 :=0
함수 recur() 를 정의하십시오. 이것은 i:=0, cur:=공백 문자열이 필요합니다.
if i is same as size of words , then ans := maximum of ans and size of cur return recur(i + 1, cur) if all characters in words[i] are unique and all characters in (cur + words[i]) are unique, then recur(i + 1, cur + words[i]) From the main method do the following: recur() return ans
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시
class Solution: def solve(self, words): ans = 0 def is_all_unique(s): return len(set(s)) == len(s) def recur(i=0, cur=""): nonlocal ans if i == len(words): ans = max(ans, len(cur)) return recur(i + 1, cur) if is_all_unique(words[i]) and is_all_unique(cur + words[i]): recur(i + 1, cur + words[i]) recur() return ans ob = Solution() words = ["xyz", "xyw", "wab", "cde"] print(ob.solve(words))
입력
["xyz", "xyw", "wab", "cde"]
출력
9