营销型网站建设搭建方法/武汉网站推广很 棒

通过数据范围想到回溯暴搜，每个字符串可以选和不选。所以直接用回溯法解决，在选的时候，需要先判断一下是否能选，最直观的想法是用一个26长度的数组

第一个版本的代码：

class Solution {
public:int maxLength(vector<string>& arr) {vector<int> hashmap(26);dfs(arr, 0, 0, hashmap);return res;}int res = 0;void dfs(vector<string>& arr, int i, int cur, vector<int> hashmap) {if(i >= arr.size()) {res = max(res, cur);return;}vector<int> tmp(hashmap);bool flag = true;for(auto c : arr[i]) {tmp[c - 'a'] ++;if(tmp[c - 'a'] > 1) {flag = false;}}if(flag) {dfs(arr, i + 1, cur + arr[i].size(), tmp);dfs(arr, i + 1, cur, hashmap);} else {dfs(arr, i + 1, cur, hashmap);}}
};

优化的方法是将hashmap改成一个BitMap，利用位运算优化

class Solution {
public:int maxLength(vector<string>& arr) {int m = 0;dfs(arr, 0, 0, m);return res;}int res = 0;void dfs(vector<string>& arr, int i, int cur, int m) {if(i >= arr.size()) {res = max(res, cur);return;}int tmp = m;bool flag = true;for(auto c : arr[i]) {int mask = 1 << (c - 'a');if (mask & tmp) {flag = false;} tmp |= mask;}if(flag) {dfs(arr, i + 1, cur + arr[i].size(), tmp);dfs(arr, i + 1, cur, m);} else {dfs(arr, i + 1, cur, m);}}
};

更优的解法是，我们首先将字符串进行预处理，然后在搜索的时候直接对字符串进行计算

非常漂亮的写法：

class Solution {
public:int maxLength(vector<string>& arr) {vector<int> masks;for (auto s : arr) {int mask = 0;for (auto c : s) {if (mask & (1 << (c - 'a'))) {mask = 0;break;} else {mask |= (1 << (c - 'a'));}}if (mask) {masks.push_back(mask);}}int res = 0;function<void(int, int)> backtrack = [&](int pos, int mask) {if (pos == masks.size()) {res = max(res, __builtin_popcount(mask));return;} if ((mask & masks[pos]) == 0) {backtrack(pos + 1, mask | masks[pos]);}backtrack(pos + 1, mask);};backtrack(0, 0);return res;}
};