class Solution {
public:
int maxLength(vector<string>& arr) {
}
};
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 <= 161 <= arr[i].length <= 26arr[i] 中只含有小写英文字母原站题解
python3 解法, 执行用时: 64 ms, 内存消耗: 18.6 MB, 提交时间: 2023-05-29 18:06:15
class Solution:
def maxLength(self, arr: List[str]) -> int:
ans = 0
masks = [0]
for s in arr:
mask = 0
for ch in s:
idx = ord(ch) - ord("a")
if ((mask >> idx) & 1): # // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解
mask = 0
break
mask |= 1 << idx # 将 ch 加入 mask 中
if mask == 0:
continue
n = len(masks)
for i in range(n):
m = masks[i]
if (m & mask) == 0: # m 和 mask 无公共元素
masks.append(m | mask)
ans = max(ans, bin(m | mask).count("1"))
return ans
javascript 解法, 执行用时: 120 ms, 内存消耗: 48.6 MB, 提交时间: 2023-05-29 18:06:02
/**
* @param {string[]} arr
* @return {number}
*/
var maxLength = function(arr) {
let ans = 0;
const masks = [0];
for (const s of arr) {
let mask = 0;
for (let i = 0; i < s.length; ++i) {
const ch = s[i].charCodeAt() - 'a'.charCodeAt();
if (((mask >> ch) & 1) !== 0) { // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解
mask = 0;
break;
}
mask |= 1 << ch; // 将 ch 加入 mask 中
}
if (mask === 0) {
continue;
}
const n = masks.length;
for (let i = 0; i < n; ++i) {
const m = masks[i];
if ((m & mask) === 0) { // m 和 mask 无公共元素
masks.push(m | mask);
ans = Math.max(ans, (m | mask).toString(2).split('0').join('').length);
}
}
}
return ans;
};
golang 解法, 执行用时: 0 ms, 内存消耗: 4.6 MB, 提交时间: 2023-05-29 18:05:44
func maxLength(arr []string) (ans int) {
masks := []int{0} // 0 对应空串
outer:
for _, s := range arr {
mask := 0
for _, ch := range s {
ch -= 'a'
if mask>>ch&1 > 0 { // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解
continue outer
}
mask |= 1 << ch // 将 ch 加入 mask 中
}
for _, m := range masks {
if m&mask == 0 { // m 和 mask 无公共元素
masks = append(masks, m|mask)
ans = max(ans, bits.OnesCount(uint(m|mask)))
}
}
}
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
java 解法, 执行用时: 9 ms, 内存消耗: 41.8 MB, 提交时间: 2023-05-29 18:05:31
// 迭代 + 位运算
class Solution {
public int maxLength(List<String> arr) {
int ans = 0;
List<Integer> masks = new ArrayList<Integer>();
masks.add(0);
for (String s : arr) {
int mask = 0;
for (int i = 0; i < s.length(); ++i) {
int ch = s.charAt(i) - 'a';
if (((mask >> ch) & 1) != 0) { // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解
mask = 0;
break;
}
mask |= 1 << ch; // 将 ch 加入 mask 中
}
if (mask == 0) {
continue;
}
int n = masks.size();
for (int i = 0; i < n; ++i) {
int m = masks.get(i);
if ((m & mask) == 0) { // m 和 mask 无公共元素
masks.add(m | mask);
ans = Math.max(ans, Integer.bitCount(m | mask));
}
}
}
return ans;
}
}
java 解法, 执行用时: 2 ms, 内存消耗: 38.7 MB, 提交时间: 2023-05-29 18:05:07
class Solution {
int ans = 0;
public int maxLength(List<String> arr) {
List<Integer> masks = new ArrayList<Integer>();
for (String s : arr) {
int mask = 0;
for (int i = 0; i < s.length(); ++i) {
int ch = s.charAt(i) - 'a';
if (((mask >> ch) & 1) != 0) { // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解
mask = 0;
break;
}
mask |= 1 << ch; // 将 ch 加入 mask 中
}
if (mask > 0) {
masks.add(mask);
}
}
backtrack(masks, 0, 0);
return ans;
}
public void backtrack(List<Integer> masks, int pos, int mask) {
if (pos == masks.size()) {
ans = Math.max(ans, Integer.bitCount(mask));
return;
}
if ((mask & masks.get(pos)) == 0) { // mask 和 masks[pos] 无公共元素
backtrack(masks, pos + 1, mask | masks.get(pos));
}
backtrack(masks, pos + 1, mask);
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 1.9 MB, 提交时间: 2023-05-29 18:04:46
func maxLength(arr []string) (ans int) {
masks := []int{}
outer:
for _, s := range arr {
mask := 0
for _, ch := range s {
ch -= 'a'
if mask>>ch&1 > 0 { // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解
continue outer
}
mask |= 1 << ch // 将 ch 加入 mask 中
}
masks = append(masks, mask)
}
var backtrack func(int, int)
backtrack = func(pos, mask int) {
if pos == len(masks) {
ans = max(ans, bits.OnesCount(uint(mask)))
return
}
if mask&masks[pos] == 0 { // mask 和 masks[pos] 无公共元素
backtrack(pos+1, mask|masks[pos])
}
backtrack(pos+1, mask)
}
backtrack(0, 0)
return
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
javascript 解法, 执行用时: 136 ms, 内存消耗: 47.9 MB, 提交时间: 2023-05-29 18:04:30
/**
* @param {string[]} arr
* @return {number}
*/
var maxLength = function(arr) {
let ans = 0;
const masks = [];
for (const s of arr) {
let mask = 0;
for (let i = 0; i < s.length; ++i) {
const ch = s[i].charCodeAt() - 'a'.charCodeAt();
if (((mask >> ch) & 1) !== 0) { // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解
mask = 0;
break;
}
mask |= 1 << ch; // 将 ch 加入 mask 中
}
if (mask > 0) {
masks.push(mask);
}
}
const backtrack = (masks, pos, mask) => {
if (pos === masks.length) {
ans = Math.max(ans, mask.toString(2).split('0').join('').length);
return;
}
if ((mask & masks[pos]) === 0) { // mask 和 masks[pos] 无公共元素
backtrack(masks, pos + 1, mask | masks[pos]);
}
backtrack(masks, pos + 1, mask);
}
backtrack(masks, 0, 0);
return ans;
};
python3 解法, 执行用时: 84 ms, 内存消耗: 16.2 MB, 提交时间: 2023-05-29 18:04:12
# 回溯 + 位运算
class Solution:
def maxLength(self, arr: List[str]) -> int:
masks = list()
for s in arr:
mask = 0
for ch in s:
idx = ord(ch) - ord("a")
if ((mask >> idx) & 1): # // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解
mask = 0
break
mask |= 1 << idx # 将 ch 加入 mask 中
if mask > 0:
masks.append(mask)
ans = 0
def backtrack(pos: int, mask: int) -> None:
if pos == len(masks):
nonlocal ans
ans = max(ans, bin(mask).count("1"))
return
if (mask & masks[pos]) == 0: # mask 和 masks[pos] 无公共元素
backtrack(pos + 1, mask | masks[pos])
backtrack(pos + 1, mask)
backtrack(0, 0)
return ans