leetcode 1239

1239. Maximum Length of a Concatenated String with Unique Characters

backtracking이랑, 이중 for문 2가지로 해결할 수 있다.

 

1. 백트래킹

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        self.maxLength = 0
        # s is 현재까지의 문자열
        # 탐색하는 문자열의 idx 
        def backtrack(s, j):
            
            if len(s) != len(set(s)):
                return
            
            self.maxLength = max(len(s), self.maxLength)

            for idx in range(j, len(arr)):
                backtrack(s + arr[idx], idx)
        
        backtrack('', 0) 
        return self.maxLength

2. 이중 for 문

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        s = [""]
        res = 0
        for i in arr:
            if len(set(i)) == len(i):
                for j in s[:]:
                    if len(i) + len(j) == len(set(i+ j)):
                        s.append(i+j)
                        if len(i+j) > res:
                            res = len(i+j)
                            
        return res