题目描述
这是 LeetCode 上的「1239. 串联字符串的最大长度」，难度为「中等」。
Tag : 「DFS」、「二进制枚举」、「模拟退火」、「随机化」、「启发式搜索」
给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。
请返回所有可行解 s 中最长长度。
示例 1：
代码语言：javascript复制输入：arr = ["un","iq","ue"]
输出：4
解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。
示例 2：
代码语言：javascript复制输入：arr = ["cha","r","act","ers"]
输出：6
解释：可能的解答有 "chaers" 和 "acters"。
示例 3：
代码语言：javascript复制输入：arr = ["abcdefghijklmnopqrstuvwxyz"]
输出：26
提示：
arr[i]中只含有小写英文字母
基本分析
根据题意，可以将本题看做一类特殊的「数独问题」：在给定的 arr 字符数组中选择，尽可能多的覆盖一个
的矩阵。
对于此类「精确覆盖」问题，换个角度也可以看做「组合问题」。
通常有几种做法：DFS、剪枝 DFS、二进制枚举、模拟退火、DLX。
其中一头一尾解法过于简单和困难，有兴趣的同学自行了解与实现。
剪枝 DFS
根据题意，可以有如下的剪枝策略：
- 预处理掉「本身具有重复字符」的无效字符串，并去重；
- 由于只关心某个字符是否出现，而不关心某个字符在原字符串的位置，因此可以将字符串使用
int进行表示； - 由于使用
int进行表示，因而可以使用「位运算」来判断某个字符是否可以被追加到当前状态中； DFS过程中维护一个total，代表后续未经处理的字符串所剩余的“最大价值”是多少，从而实现剪枝；- 使用
lowbit计算某个状态对应的字符长度是多少； - 使用「全局哈希表」记录某个状态对应的字符长度是多少（使用
static修饰，确保某个状态在所有测试数据中只会被计算一次）； - 【未应用】由于存在第
点这样的「更优性剪枝」，理论上我们可以根据「字符串所包含字符数量」进行从大到小排序，然后再进行 DFS 这样效果理论上会更好。想象一下如果存在一个包含所有字母的字符串，先选择该字符串，后续所有字符串将不能被添加，那么由它出发的分支数量为
；而如果一个字符串只包含单个字母，先决策选择该字符串，那么由它出发的分支数量必然大于
。但该策略实测效果不好，没有添加到代码中。
代码：
代码语言：javascript复制class Solution {
// 本来想使用如下逻辑将「所有可能用到的状态」打表，实现 O(1) 查询某个状态有多少个字符，但是被卡了
// static int N = 26, M = (1 << N);
// static int[] cnt = new int[M];
// static {
// for (int i = 0; i < M; i ) {
// for (int j = 0; j < 26; j ) {
// if (((i >> j) & 1) == 1) cnt[i] ;
// }
// }
// }
static Map<Integer, Integer> map = new HashMap<>();
int get(int cur) {
if (map.containsKey(cur)) {
return map.get(cur);
}
int ans = 0;
for (int i = cur; i > 0; i -= lowbit(i)) ans ;
map.put(cur, ans);
return ans;
}
int lowbit(int x) {
return x & -x;
}
int n;
int ans = Integer.MIN_VALUE;
int[] hash;
public int maxLength(List<String> _ws) {
n = _ws.size();
HashSet<Integer> set = new HashSet<>();
for (String s : _ws) {
int val = 0;
for (char c : s.toCharArray()) {
int t = (int)(c - 'a');
if (((val >> t) & 1) != 0) {
val = -1;
break;
}
val |= (1 << t);
}
if (val != -1) set.add(val);
}
n = set.size();
if (n == 0) return 0;
hash = new int[n];
int idx = 0;
int total = 0;
for (Integer i : set) {
hash[idx ] = i;
total |= i;
}
dfs(0, 0, total);
return ans;
}
void dfs(int u, int cur, int total) {
if (get(cur | total) <= ans) return;
if (u == n) {
ans = Math.max(ans, get(cur));
return;
}
// 在原有基础上，选择该数字（如果可以）
if ((hash[u] & cur) == 0) {
dfs(u 1, hash[u] | cur, total - (total & hash[u]));
}
// 不选择该数字
dfs(u 1, cur, total);
}
}
二进制枚举
首先还是对所有字符串进行预处理。
然后使用「二进制枚举」的方式，枚举某个字符串是否被选择。
举个
