【leetcode】串联字符串的最大长度(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] 中只含有小写英文字母

思路分析：

大意就是要找最长长度的字符串s，并且s每个字符都不相同。根据提示，每个字符串都只含有小写字母，那么可以想到用一个长度为26的整型数组作为哈希表。对于每个子串，我们需要一个个尝试串联。用dfs遍历每个子串，设arr[cur]为当前子串，len为子串长度，有三种情况。

当前子串满足串联条件，取该子串，则len1 = len + dfs(cur+1);当前子串满足串联条件，不取该子串，len2 = dfs(cur+1);当前子串不满足串联条件，不去该字串，只能return dfs(cur+1).

最后，我们取最大长度 return max(len1, len2); 我们在遍历子串的时候需要更新哈希表，可如果dfs返回一条路，选择另一条路时，如果不回溯哈希表让其变成原本的样子，结果就不正确了。因此在每一次遍历的状态需要加上哈希表。在每次遍历时，我们新建一个哈希表用于更新。如果选择第一种情况，我们就把新的哈希表递归下去，否则就把原来的哈希表递归下去。下面上代码。

class Solution { public: int dfs(int cur, vector<string>& arr, vector<int> &m) { if(cur >= arr.size()) { return 0; } vector<int> t(m); //建一个新哈希表 for(int i = 0;i < arr[cur].length();i++) { int id = arr[cur][i]-'a'; if(t[id]) return dfs(cur+1,arr, m); //情况3 t[id]++; //更新新表的哈希表 } int len1 = arr[cur].length() + dfs(cur+1, arr, t); //情况1，将新表递归下去 int len2 = dfs(cur+1, arr, m); //情况2 return max(len1, len2); } int maxLength(vector<string>& arr) { vector<int> m(27,0); return dfs(0, arr, m); } };

优化：位压缩

先分析一下题意：我们需要枚举所有单词的组合情况，并要保证该情况中所有字符都只出现一次。对于枚举所有情况，arr数组最多只有16，我们可以想到用一个16位的二进制位表示。这个二进制位可以用 int 存，因为 int 的范围在 2^31 。对于字符，我们也可以用一个26位的二进制位表示。 假设 n = 3，i 需要从 000 到 111 枚举所有情况，也就是在 [0, 2ⁿ-1) 范围。 对于每种情况(i)，我们需要初始化一个哈希 vis 和对于当前情况长度的计数cnt. 然后，我们对于 i 遍历每个二进制位看看哪个位取了1，即哪个位选了单词。这里用(i>>j)&1获取到 i 二进制中的第 (j-1) 位的值。 若选择了该单词((i>>j)&1 == 1) 就判断遍历该单词所有的字符，看看vis中有没有已经存在的字符。 若vis存在该字符，退出循环；不存在，计数； 之后，对每种情况得到的cnt，取最大的那个。

class Solution { public: int maxLength(vector<string>& arr) { int n = arr.size(); int ans = 0; for(int i = 0;i < (1<<n);i++){ //枚举所有情况 int vis = 0; //判断字符是否存在的二进制位压缩 int cnt = 0; for(int j = 0;j < n;j++){ bool flag = 0; if((i>>j)&1){ //选该单词，(i>>j)表示在i二进制中的第(j-1)位 for(int k = 0;k < arr[j].length();k++){ //遍历该单词所有字符 int id = arr[j][k]-'a'; int pos = 1<<id; //获取该字符对应二进制位的位置(如'b', id = 1, pos二进制就是10) if(vis&pos){ //获取vis中pos位置的二进制位 flag = 1; break; } else{ vis |= pos; //将vis在pos上的二进制位置1 } } if(flag) break; cnt += arr[j].length(); ans = max(ans,cnt); } } } return ans; } };