1239.串联字符串的*大长度 关于字符串的回溯算法!
一个优秀的内容风控解决方案应该是怎样的?
信息传播的媒介与形态五花八门,对于互联网平台来说,保障内容安全越来越难。当下互联网平台面临哪些困境?7月3日,腾讯安全思享会,带大家一起探索亟需的答案,限额报名
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>