코딩 테스트 및 알고리즘/leetcode for google
leetcode medium : Maximum Length of a Concatenated String with Unique Characters
띠리링구
2022. 10. 29. 18:14
https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/
Maximum Length of a Concatenated String with Unique Characters - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
class Solution:
def maxLength(self, arr: List[str]) -> int:
unique_sets = [set(element) for element in arr if len(element) == len(set(element))]
all_possible_combinations = [set()]
for single_set in unique_sets:
apc_copy = all_possible_combinations.copy()
for found_before in apc_copy:
if not single_set & found_before:
all_possible_combinations.append(single_set | found_before)
answer = max(len(comb) for comb in all_possible_combinations)
return answer
지금까지 본 것들을 가지고 만들 수 있는 문자 조합 set를 계속 유지한다.
인풋 array를 처음부터 끝까지 하나씩 보면서 "지금까지 본 것들을 가지고 만들 수 있는 문자 조합 set"를 만들어나가면 된다.
상수 조건이 숫자가 매우 작은걸 보면 노가다(전문용어로 brute force 혹은 backtracking)문제인걸 쉽게 알 수 있다.