LeetCode 1239. 串联字符串的最大长度

Categories:

题目描述
思路分析
1. 解法一：位掩码 + 回溯（推荐）
相似题目

题目描述

✅ 1239. 串联字符串的最大长度

思路分析

解法一：位掩码 + 回溯（推荐）

核心思路：

将每个字符串转换为 26 位掩码，若内部有重复字母则丢弃。

回溯枚举是否选择当前字符串，若与当前掩码无冲突则合并。

记录最大可用位数（长度）。

复杂度分析：

时间复杂度：O(2^n)，其中 n 为有效字符串数量。

空间复杂度：O(n)，递归栈与掩码数组。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int maxLength(List<String> arr) {
        List<Integer> masks = new ArrayList<>();
        List<Integer> lens = new ArrayList<>();

        for (String s : arr) {
            int mask = 0;
            boolean ok = true;
            for (int i = 0; i < s.length(); i++) {
                int bit = 1 << (s.charAt(i) - 'a');
                if ((mask & bit) != 0) {
                    ok = false;
                    break;
                }
                mask |= bit;
            }
            if (ok) {
                masks.add(mask);
                lens.add(s.length());
            }
        }

        return dfs(masks, lens, 0, 0);
    }

    private int dfs(List<Integer> masks, List<Integer> lens, int idx, int mask) {
        if (idx == masks.size()) {
            return 0;
        }

        int best = dfs(masks, lens, idx + 1, mask);

        int next = masks.get(idx);
        if ((mask & next) == 0) {
            best = Math.max(best, lens.get(idx) + dfs(masks, lens, idx + 1, mask | next));
        }
        return best;
    }
}

func maxLength(arr []string) int {
    masks := make([]int, 0)
    lens := make([]int, 0)

    for _, s := range arr {
        mask := 0
        ok := true
        for i := 0; i < len(s); i++ {
            bit := 1 << (s[i] - 'a')
            if mask&bit != 0 {
                ok = false
                break
            }
            mask |= bit
        }
        if ok {
            masks = append(masks, mask)
            lens = append(lens, len(s))
        }
    }

    return dfs(masks, lens, 0, 0)
}

func dfs(masks []int, lens []int, idx int, mask int) int {
    if idx == len(masks) {
        return 0
    }

    best := dfs(masks, lens, idx+1, mask)

    next := masks[idx]
    if mask&next == 0 {
        val := lens[idx] + dfs(masks, lens, idx+1, mask|next)
        if val > best {
            best = val
        }
    }
    return best
}

相似题目

题目	难度	考察点
318. 最大单词长度乘积	中等	位掩码
1255. 得分最高的单词集合	困难	位掩码、回溯
78. 子集	中等	回溯
46. 全排列	中等	回溯
1239. 串联字符串的最大长度	中等	位掩码

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/65561109