LeetCode 1239. 串联字符串的最大长度（回溯/动态规划）数据结构与算法Michael是个半路程序员-

1. 题目

给定一个字符串数组 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] 中只含有小写英文字母 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 回溯超时解

class Solution { int maxlen = 0; public: int maxLength(vector<string>& arr) { int count = 0; dfs(arr, count, 0, 0); return maxlen; } void dfs(vector<string>& arr, int count, int idx, int len) { bool ok; for(int i = idx, j; i < arr.size(); ++i) { //不应该加这层循环，超时了！！！       ok = true; for(j = 0; j < arr[i].size(); ++j) { if((count>>(arr[i][j]-'a'))&1)//已经存在该字符 {         ok = false; break; } } if(ok) { for(j = 0; j < arr[i].size(); ++j) {         count |= (1<<(arr[i][j]-'a')); }        len += arr[i].size();        maxlen = max(maxlen, len); dfs(arr, count, idx+1, len);        len -= arr[i].size(); for(j = 0; j < arr[i].size(); ++j) {         count &= ~(1<<(arr[i][j]-'a')); } } } } }; 

2.2 回溯优化

• 把每个字符的状态存在 int 的二进制位上
• 每个单词两种选择，选或者不选

class Solution { int maxlen = 0; public: int maxLength(vector<string>& arr) { dfs(arr, 0, 0, 0); return maxlen; } void dfs(vector<string>& arr, int count, int i, int len) {         maxlen = max(maxlen, len); if(i == arr.size()) return; int j, origin = count; for(j = 0; j < arr[i].size(); ++j) { if((count>>(arr[i][j]-'a'))&1)//已经存在该字符 { return dfs(arr, origin, i+1, len);//这个单词不选 }             count |= (1<<(arr[i][j]-'a')); } dfs(arr, origin, i+1, len);//该单词不选        dfs(arr, count, i+1, len+arr[i].size()); //该单词选 } }; 

8 ms 8.2 MB

2.3 动态规划

class Solution { public: int maxLength(vector<string>& arr) { int i, j, n = arr.size(), maxlen = 0, state, nextstate; bool ok;         map<int,int> dp;//字符数状态int表示，最大长度         dp[0] = 0; for(i = 0; i < n; ++i) { for(auto it = dp.rbegin(); it != dp.rend(); ++it) { //逆序遍历，新生成的状态加在末尾了不会干扰本次 //本题正序，也可以，因为同一个单词加2次肯定重复， //不会新生成下一个state，但是无畏的遍历多了，耗时788 ms 13.8 MB                 state = it->first;                 nextstate = state;                 ok = true; for(j = 0; j < arr[i].size(); ++j) { if((nextstate>>(arr[i][j]-'a'))&1)//该位存在 {                         ok = false; break; }                     nextstate |= (1<<(arr[i][j]-'a')); } if(ok) {                     dp[nextstate] = max(dp[nextstate], int(dp[state]+arr[i].size()));                     maxlen = max(maxlen, dp[nextstate]); } } } return maxlen; } }; 

184 ms 13.6 MB