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

https://leetcode-cn.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/solution/1239chuan-lian-zi-fu-chuan-de-zui-da-cha-7weh/

难度：中等

题目：

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

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

提示：

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

示例：

<pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px; border-radius: 5px; box-shadow: rgba(0, 0, 0, 0.55) 0px 2px 10px;">`示例 1：

输入：arr = ["un","iq","ue"]

输出：4

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

示例 2：

输入：arr = ["cha","r","act","ers"]

输出：6

解释：可能的解答有 "chaers" 和 "acters"。

示例 3：

输入：arr = ["abcdefghijklmnopqrstuvwxyz"]

输出：26` </pre>

分析

当看到题目涉及排列组合求最优、最长、并且需要选择加入这类条件时，就要考虑回溯方法了。 这道题由于arr.length <= 16 且仅包含26个小写英文字母那么复杂度会底很多。

首先，我们在接收到arr列表后，先对列表中每一个元素是否存在重复值进行过滤， 这样可以节省回溯过程中不必要的判断与剪枝操作。

之后开始通过index逐步递归判断最长字符串，大家日常遇到的可能列表的回溯比较多，需要先append，再pop。

但这道题是字符串所以只需要字符串拼接即可，总体来说是一道比较简单的回溯题目。

解题：

<pre class="custom" data-tool="mdnice编辑器" style="margin-top: 10px; margin-bottom: 10px; border-radius: 5px; box-shadow: rgba(0, 0, 0, 0.55) 0px 2px 10px;">`class Solution:

def maxLength(self, arr):

arr = [i for i in arr if len(set(i)) == len(i)]

ln = len(arr)

ret = 0

def dfs(strs, index):
        nonlocal ret
        if ln <= index:
            ret = max(ret, len(strs))
            return
        if not set(arr[index]) & set(strs):
            dfs(strs + arr[index], index + 1)
        dfs(strs, index + 1)
    dfs('', 0)
    return ret` </pre>