题目形容
这是 LeetCode 上的 1239. 串联字符串的最大长度 ，难度为 中等。
Tag : 「DFS」、「二进制枚举」、「模拟退火」、「随机化」、「启发式搜寻」
给定一个字符串数组 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 <= arr.length <= 16$
- $1 <= arr[i].length <= 26$
arr[i]中只含有小写英文字母
根本剖析
依据题意，能够将本题看做一类非凡的「数独问题」：在给定的 arr 字符数组中抉择，尽可能多的笼罩一个 $1 \times 26$ 的矩阵。
对于此类「准确笼罩」问题，换个角度也能够看做「组合问题」。
通常有几种做法：DFS、剪枝 DFS、二进制枚举、模拟退火、DLX。
其中一头一尾解法过于简略和艰难，有趣味的同学自行理解与实现。
剪枝 DFS
依据题意，能够有如下的剪枝策略：
- 预处理掉「自身具备反复字符」的有效字符串，并去重；
- 因为只关怀某个字符是否呈现，而不关怀某个字符在原字符串的地位，因而能够将字符串应用
int进行示意； - 因为应用
int进行示意，因此能够应用「位运算」来判断某个字符是否能够被追加到以后状态中； DFS过程中保护一个total，代表后续未经解决的字符串所残余的“最大价值”是多少，从而实现剪枝；- 应用
lowbit计算某个状态对应的字符长度是多少； - 应用「全局哈希表」记录某个状态对应的字符长度是多少（应用
static润饰，确保某个状态在所有测试数据中只会被计算一次）； - 【未利用】因为存在第 $4$ 点这样的「更优性剪枝」，实践上咱们能够依据「字符串所蕴含字符数量」进行从大到小排序，而后再进行
DFS这样成果实践上会更好。设想一下如果存在一个蕴含所有字母的字符串，先抉择该字符串，后续所有字符串将不能被增加，那么由它登程的分支数量为 $0$；而如果一个字符串只蕴含单个字母，先决策抉择该字符串，那么由它登程的分支数量必然大于 $0$。但该策略实测成果不好，没有增加到代码中。
代码：
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); }}二进制枚举
首先还是对所有字符串进行预处理。
而后应用「二进制枚举」的形式，枚举某个字符串是否被抉择。
举个，$(110)_{2}$ 代表抉择前两个字符串，$(011)_{2}$ 代表抉择后两个字符串，这样咱们便能够枚举出所有组合计划。
代码：
class Solution { 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; Integer[] 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 Integer[n]; int idx = 0; for (Integer i : set) hash[idx++] = i; for (int i = 0; i < (1 << n); i++) { int cur = 0, val = 0; for (int j = 0; j < n; j++) { if (((i >> j) & 1) == 1) { if ((cur & hash[j]) == 0) { cur |= hash[j]; val += get(hash[j]); } else { cur = -1; break; } } } if (cur != -1) ans = Math.max(ans, val); } return ans; }}模拟退火
事实上，能够将原问题看作求「最优前缀序列」问题，从而应用「模拟退火」进行求解。
具体的，咱们能够定义「最优前缀序列」为 组成最优解所用到的字符串均呈现在排列的后面。
举个，如果形成最优解应用到的字符串汇合为 [a,b,c]，那么对应 [a,b,c,...]、[a,c,b,...] 均称为「最优前缀序列」。
不难发现，答案与最优前缀序列是一对多关系，这领导咱们能够将「参数」调得宽松一些。
具备「一对多」关系的问题非常适宜应用「模拟退火」，应用「模拟退火」能够轻松将本题 arr.length 数据范畴回升到 $60$ 甚至以上。
调整成比拟宽松的参数能够跑赢「二进制枚举」，但为了当前减少数据不容易被 hack，还是应用 N=400 & fa=0.90 的搭配。
「模拟退火」的几个参数的作用在 这里 说过了，不再赘述。
代码：
class Solution { 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; Random random = new Random(20210619); double hi = 1e4, lo = 1e-4, fa = 0.90; int N = 400; int calc() { int mix = 0, cur = 0; for (int i = 0; i < n; i++) { int hash = ws[i]; if ((mix & hash) == 0) { mix |= hash; cur += get(hash); } else { break; } } ans = Math.max(ans, cur); return cur; } void shuffle(int[] nums) { for (int i = n; i > 0; i--) { int idx = random.nextInt(i); swap(nums, idx, i - 1); } } void swap(int[] nums, int a, int b) { int c = nums[a]; nums[a] = nums[b]; nums[b] = c; } void sa() { shuffle(ws); for (double t = hi; t > lo; t *= fa) { int a = random.nextInt(n), b = random.nextInt(n); int prev = calc(); swap(ws, a, b); int cur = calc(); int diff = cur - prev; if (Math.log(-diff / t) > random.nextDouble()) swap(ws, a, b); } } int[] ws; public int maxLength(List<String> _ws) { // 预处理字符串：去重，剔除有效字符 // 后果这一步后：N 能够降落到 100；fa 能够降落到 0.70，耗时约为 78 ms // 为了预留未来增加测试数据，题解还是放弃 N = 400 & fa = 0.90 的配置 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; ws = new int[n]; int idx = 0; for (Integer i : set) ws[idx++] = i; while (N-- > 0) sa(); return ans; }}最初
这是咱们「刷穿 LeetCode」系列文章的第 No.1239 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布