1239.串联字符串的最大长度

0.0.1. 题目

给定一个字符串数组arr，字符串s是将arr某一子序列字符串连接所得的字符串，如果s中的每一个字符都只出现过一次，那么它就是一个可行解。

请返回所有可行解s中最长长度。

示例 1：

1
2
3

输入：arr = ["un","iq","ue"]
输出：4
解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。

示例 2：

1
2
3

输入：arr = ["cha","r","act","ers"]
输出：6
解释：可能的解答有 "chaers" 和 "acters"。

示例 3：

1 2	输入：arr = ["abcdefghijklmnopqrstuvwxyz"] 输出：26

提示：

1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] 中只含有小写英文字母

0.0.2. 我的解法(79/85)

很遗憾。。。

class Solution(object):
    def maxLength(self, arr):
        """
        :type arr: List[str]
        :rtype: int
        """

        if not arr:
            return 0
        if len(arr) == 1:
            return len(arr[0])

        n = len(arr)
        max_ = 0
        act = ""
        def isAppeared(str1,str2):
            if len(str1) > len(str2):
                str1, str2 = str2, str1
            for ch in str1:
                if ch in str2:
                    return True
            return False
        def isPure(str1):
            if len(str1) == len(set(str1)):
                return True
            return False

        for i in range(n):
            if isPure(arr[i]):
                max_ = max(max_,len(arr[i]))
                act = arr[i]
            for j in range(i+1,n):
                if not isAppeared(act,arr[j]) and isPure(arr[j]):
                    act = act + arr[j]
                    max_ = max(max_,len(act))
        return max_

0.0.3. 好的解法

参考:benhao

0.0.3.1. 直白质朴法

我的思路总体和这个是一致的

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        def validStr(string):
            return len(set(string)) == len(string)
        
        dp = []
        for s in arr:
            if not validStr(s):
                continue
            for s_ in dp:
                if validStr(s_ + s):
                    dp.append(s_ + s)
            dp.append(s)
        return len(max(dp,key=len)) if dp else 0

0.0.4. 0.0.5. 回溯法

NoBug

回溯算法，采用递归实现

class Solution():
    def maxLength(self, arr):

        t = []
        for s in arr:
            if len(set(s)) == len(s):
                t.append(s)
        arr = t[:]

        def dfs(i, tmp):

            if i >= len(arr):
                return len(tmp)
            else:
                if not (set(tmp) & set(arr[i])):
                    return max(dfs(i+1,tmp+arr[i]),dfs(i+1,tmp))
                else:
                    return dfs(i + 1, tmp)

        l=dfs(0,'')
        return l