开发者社区> 清风Python> 正文

1239.串联字符串的最大长度 关于字符串的回溯算法!

简介: 1239.串联字符串的最大长度 关于字符串的回溯算法!
+关注继续查看

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>




版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14897 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
16424 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
19795 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
29129 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
16640 0
+关注
183
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载