LeetCode——1239. 串联字符串的最大长度（Java）

题目描述

题干：
给定一个字符串数组 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

算法的思路为先将各个字符进行判断是否可以进行组合，然后在采用一个回溯算法来处理多个字符的比较

正确代码

class Solution {

    int ans = 0;

    //回溯+位运算
    public int maxLength(List<String> arr) {
        List<Integer> masks = new ArrayList<>();
        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 = 0;
                    break;
                }
                //将当前位置数字置为1
                mask |= 1 << ch;
            }
            if (mask > 0) {
                masks.add(mask);
            }
        }
        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) {
            backtrack(masks,pos + 1, mask | masks.get(pos));
        }
    }
}

总结

这种采用二进制来保存对比的思路确实可以解决很多重复或者其他规律的问题

如果文章存在问题或者有其他更好的题解，欢迎在评论区斧正和评论，各自努力，你我最高处见

LeetCode——1239. 串联字符串的最大长度（Java）

原文：https://www.cnblogs.com/bc-song/p/14902808.html