LeetCode-Go 题解 1239位掩码 DFS 求解最大无重复字符连接串长度【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇技术指南以 LeetCode-Go 仓库中 1239. Maximum Length of a Concatenated String with Unique Characters 题解文档 为主体深入剖析该题将字符串映射为 26 位二进制掩码 深度优先搜索枚举子序列的经典解法。读完本文你将掌握如何用uint32位掩码高效表示字符集合、如何用按位与运算做冲突检测以及如何基于仓库内的源码与测试用例独立验证算法正确性。题目描述给定一个字符串数组arr。字符串s是由arr中某个子序列sub-sequence的字符串拼接concatenation而成并且s中的每个字符都必须是唯一的unique characters。请返回满足条件的s的最大可能长度maximum possible length。示例示例 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 161 arr[i].length 26arr[i]仅包含小写英文字母核心思路把字符串压缩成 26 位二进制掩码题目对唯一字符的要求非常严格拼接结果s中任何字符都不能重复出现。由于输入仅包含小写英文字母共 26 个我们可以把每个字符串压缩为一个 26 位的二进制串mask字符串中出现过的字符对应位标记为 1字符串中未出现的字符对应位标记为 0。这一映射有两条极其有用的性质自重复检测如果一个字符串内部本身就含有重复字符那么它掩码中 1 的个数一定不等于字符串长度。因此len(s) ! bits.OnesCount32(mask)可以直接判断该字符串是否自洁。互不冲突检测如果两个字符串各自的字符都不重复且它们拼接后仍不产生重复字符那么这两个掩码按位与的结果必然为 0mask1 mask2 0说明二者的 1 位完全不重叠、字符集合互补。借助这两条性质我们可以把字符串拼接这个看似字符串层面的操作完全降维成整数的按位与 / 按位或运算再配合深度优先搜索枚举所有可行子序列组合即可求出最长可行解的长度。算法流程分解第一步构建掩码并过滤自重复字符串对应仓库源码 题解实现 中的maxLength函数前半段c, res : []uint32{}, 0 for _, s : range arr { var mask uint32 for _, c : range s { mask mask | 1(c-a) // 将字符 c 对应的位标记为 1 } if len(s) ! bits.OnesCount32(mask) { // 如果字符串本身带有重复的字符需要排除 continue } c append(c, mask) }关键细节c - a将字符转换为 025 的索引1(c-a)得到该字符对应的唯一二进制位bits.OnesCount32(mask)来自 Go 标准库math/bits统计 32 位整数中 1 的个数即字符串中不同字符的数量若len(s) ! bits.OnesCount32(mask)说明字符串内部有重复字符这类字符串不可能出现在任何可行解中因为拼接结果要求每个字符唯一直接跳过。这一步是重要的剪枝arr中可能混入aa、abab这类自身就带重复的字符串提前过滤可以显著缩小后续 DFS 的搜索空间。第二步DFS 枚举所有互不冲突的子序列过滤完成后问题转化为在掩码数组c中选取若干互不冲突两两按位与为 0的掩码使所有选中掩码的 1 位总数最大。这正是典型的子集枚举问题用深度优先搜索解决func dfs(c []uint32, index int, mask uint32, res *int) { *res max(*res, bits.OnesCount32(mask)) for i : index; i len(c); i { if maskc[i] 0 { dfs(c, i1, mask|c[i], res) } } return }搜索策略要点index表示从掩码数组的哪个位置开始继续选取保证每个子序列组合只被枚举一次组合而非排列顺序无关mask c[i] 0是可行性剪枝当前已选字符集合与候选字符串的字符集合无交集时才允许拼接选中后通过mask | c[i]合并字符集合传入下一层递归每进入一层都用bits.OnesCount32(mask)统计当前拼接串长度因为所有字符唯一1 的个数就是字符串长度并更新全局最大值*res。入口调用为dfs(c, 0, 0, res)从空集出发初始掩码为 0最长长度为 0。完整 Go 实现以下代码与仓库 题解实现文件 完全一致增加中文注释package leetcode import ( math/bits ) func maxLength(arr []string) int { c, res : []uint32{}, 0 for _, s : range arr { var mask uint32 for _, c : range s { mask mask | 1(c-a) // 标记字符 c 在掩码中对应的位 } if len(s) ! bits.OnesCount32(mask) { // 如果字符串本身带有重复的字符需要排除 continue } c append(c, mask) } dfs(c, 0, 0, res) return res } func dfs(c []uint32, index int, mask uint32, res *int) { *res max(*res, bits.OnesCount32(mask)) for i : index; i len(c); i { if maskc[i] 0 { // 两个掩码按位与为 0说明字符集合互补可以拼接 dfs(c, i1, mask|c[i], res) } } return } func max(a, b int) int { if a b { return a } return b }实现细节仓库 go.mod 声明 Go 版本为 1.19该版本标准库尚未提供内置的max泛型函数Go 1.21 才引入因此题解在包内自行定义了max(a, b int) int辅助函数。测试用例与运行验证仓库为本题提供了完整的单元测试文件 1239 测试用例采用本仓库统一的参数-答案结构组织测试数据package leetcode import ( fmt testing ) type question1239 struct { para1239 ans1239 } // para 是参数 // one 代表第一个参数 type para1239 struct { arr []string } // ans 是答案 // one 代表第一个答案 type ans1239 struct { one int } func Test_Problem1239(t *testing.T) { qs : []question1239{ { para1239{[]string{un, iq, ue}}, ans1239{4}, }, { para1239{[]string{cha, r, act, ers}}, ans1239{6}, }, { para1239{[]string{abcdefghijklmnopqrstuvwxyz}}, ans1239{26}, }, { para1239{[]string{aa, bb}}, ans1239{0}, }, } fmt.Printf(------------------------Leetcode Problem 1239------------------------\n) for _, q : range qs { _, p : q.ans1239, q.para1239 fmt.Printf(【input】:%v 【output】:%v\n, p, maxLength(p.arr)) } fmt.Printf(\n\n\n) }除了题目给出的 3 个示例测试还额外覆盖了一个重要的边界用例[aa, bb]→ 0两个字符串内部都含重复字符过滤后掩码数组为空DFS 不会产生任何拼接结果最终返回 0。这验证了空拼接串 也是合法可行解的边界情形——所有字符串都被排除时最长长度为 0。仓库根目录的 gotest.sh 提供了统一的多包覆盖率测试命令go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以只针对本题所在包运行go test -v ./leetcode/1239.Maximum-Length-of-a-Concatenated-String-with-Unique-Characters/复杂度分析时间复杂度掩码构建阶段遍历每个字符串的每个字符为 O(N × L)其中 N len(arr)≤ 16L ≤ 26字符串最长 26 个不同小写字母DFS 阶段最坏情况下所有字符串自身无重复且两两互不冲突需要枚举全部 2^N 种子集组合即 O(2^N)。由于 N ≤ 16搜索空间最多 65536 种状态规模极小。空间复杂度掩码数组存储 O(N) 个uint32DFS 递归深度最多 N总空间复杂度 O(N)。关键点总结26 位掩码是本题的核心抽象uint32整数即可完整表达任意小写字母字符串的字符集合比较与合并都退化为常数时间的位运算。两条判定准则bits.OnesCount32(mask)与字符串长度比较可排除自重复字符串mask c[i] 0可判定两个字符串拼接后是否仍满足唯一性。DFS 保证枚举完备性以索引递增的方式遍历掩码数组确保每个可行子序列组合恰好被考虑一次配合冲突剪枝规模极小的 N≤ 16下可轻松穷举出全局最优解。边界情形所有字符串均被过滤时返回 0空串也是合法可行解仓库测试用例[aa, bb] → 0对此做了明确验证。该位掩码 DFS/回溯的组合是算法面试中处理小规模子集枚举 字符唯一性约束类问题的通用范式理解本题的掩码抽象与剪枝策略后可迁移到类似的字符串子序列、子集组合类问题中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考