1239. 串联字符串的最大长度
题目描述
给定一个字符串数组 arr
,字符串 s
是将 arr
的含有 不同字母 的 子序列 字符串 连接 所得的字符串。
请返回所有可行解 s
中最长长度。
子序列 是一种可以从另一个数组派生而来的数组,通过删除某些元素或不删除元素而不改变其余元素的顺序。
示例 1:
输入:arr = ["un","iq","ue"] 输出:4 解释:所有可能的串联组合是: - "" - "un" - "iq" - "ue" - "uniq" ("un" + "iq") - "ique" ("iq" + "ue") 最大长度为 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]
中只含有小写英文字母
解法
方法一:位运算 + 状态压缩
状态压缩,用一个 $32$ 位数记录字母的出现情况,masks
存储之前枚举的字符串。
时间复杂度 $O(2^n + L)$,空间复杂度 $O(2^n)$。其中 $n$ 和 $L$ 分别是字符串数组的长度和字符串数组中字符串的长度之和。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|