【2021/6/19 刷题笔记】串联字符串的最大长度与回溯法

2021/6/19 23:26:54

编程Tag： 作用域 LEN res arr sub 2021 19 刷题 cur

本文主要是介绍【2021/6/19 刷题笔记】串联字符串的最大长度与回溯法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

串联字符串的最大长度
- 【题目】
- 【我的方法】
- 【其他方法】
- - 扩展之nonlocal 关键字

串联字符串的最大长度

【题目】

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

示例 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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

【我的方法】

暴力。。。

先把所有串联组合列出来
一个个判断是否为可行解，并更新最长长度

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        res=0
        n=len(arr)
        arr.append('')
        for i in range(n):
            for j in range(n,len(arr)):
                arr.append(arr[i]+arr[j])
        # print(arr)
        for i in range(n,len(arr)):
            mp=set()
            for j in arr[i]:
                if j not in mp:
                    mp.add(j)
                else:
                    mp=set()
                    break
            # print(arr[i])
            res=max(res,len(mp))
        return res
# 执行用时：1332 ms, 在所有 Python3 提交中击败了12.62%的用户
# 内存消耗：25.2 MB, 在所有 Python3 提交中击败了6.98%的用户

【其他方法】

使用回溯法（因为答案来自数组中的字符串组合的某种结果，且需要遍历数组中所有元素的组合方式, 从这些组合中找到既满足字符唯一, 又是最长的结果即可）。

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        res=0

        def if_add(sub1,sub2):  # 判断是否能合并sub1和sub2
            for i in sub2:
                if i in sub1:
                    return False
            return True

        def if_distinct(sub):  # 判断自身是否为可行解
            return len(set(sub))==len(sub)
        
        def backtrack(sub,cur,arr):  # 回溯
            nonlocal res
            if cur==len(arr):
                # print(sub,cur)
                res=max(res,len(sub))
                return
            
            if if_distinct(arr[cur]) and if_add(sub,arr[cur]):  # 剪枝
                backtrack(sub+arr[cur],cur+1,arr)
            backtrack(sub,cur+1,arr)
        
        backtrack('',0,arr)
        return res
# 执行用时：96 ms, 在所有 Python3 提交中击败了76.08%的用户
# 内存消耗：15 MB, 在所有 Python3 提交中击败了69.77%的用户

trick之判断自身是否为可行解时，用到了set去重

扩展之nonlocal 关键字

Python 对于变量的查找顺序为：局部的命名空间（Local） -> 全局命名空间（Global） -> 内置命名空间（Built-in）。

# var1 是全局名称
var1 = 5
def some_func():
 
    # var2 是局部名称
    var2 = 6
    def some_inner_func():
 
        # var3 是内嵌的局部名称
        var3 = 7

当内部作用域想修改外部作用域的变量时，就要用到 global 和 nonlocal 关键字。
如果要修改嵌套作用域（enclosing 作用域，外层非全局作用域）中的变量则需要 nonlocal 关键字
- Enclosing作用域：包含了非局部(non-local)也非全局(non-global)的变量。
  - 比如两个嵌套函数，一个函数（或类） A 里面又包含了一个函数 B ，那么对于 B 中的名称来说 A 中的作用域就为 nonlocal。

【部分内容参考自】

Python3 命名空间和作用域：https://www.runoob.com/python3/python3-namespace-scope.html
【赤小豆】python 朴素的回溯法：https://leetcode-cn.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/solution/chi-xiao-dou-python-po-su-de-hui-su-fa-b-yosv/

这篇关于【2021/6/19 刷题笔记】串联字符串的最大长度与回溯法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！