leetcode-160周赛-5240-串联字符串的最大长度

题目描述：

 自己的提交：O(2**n∗n∗m)，m 为字符串长度

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        from collections import Counter
        if not arr:return 0
        res = set()
        n = len(arr)
        def helper(idx, tmp):
            if len(tmp)>26:
                return
            count = Counter(tmp)
            if all(i==1 for i in count.values()):
                res.add(tmp)
            for i in range(idx, n):
                helper(i+1, tmp + arr[i])
        helper(0, "")
        maxi = 0
        # print(res)
        for i in res:
            maxi = max(maxi,len(i))
        return maxi

另：动态规划

from collections import Counter
class Solution:
    def sToNum(self, s):
        ans = 0
        for c in s:
            ans |= 1<<(ord(c) - ord("a"))
        return ans
    def count(self, num):
        ans = 0
        while num:
            num -= num&(-num)
            ans += 1
        return ans
    def maxLength(self, A):
        A = [word for word in A if len(word) == len(set(word))]
        sA = [self.sToNum(word) for word in A]

        aSet = set([0])
        for word in sA:
            newS = set(aSet)
            for s in aSet:
                if not (s & word):
                    newS.add(s | word)
            aSet = newS
            # print (aSet)
        return max(self.count(word) for word in aSet)