因为每个单词可以选或者不选，所以可以用回溯暴搜的方法，枚举所有满足要求的子串，然后求max，这个算法的时间复杂度是指数级别的。
class Solution { public: int maxLength(vector<string>& arr) { unordered_set<char> st; dfs(arr,0,st,0); return res; } int res = 0; void dfs(vector<string>& arr, int index, unordered_set<char>& st, int count){ if(index==arr.size()){ res = max(res,count); return; } string word = arr[index]; if(check1(word,st)){ for(auto c:word) st.insert(c); dfs(arr,index+1,st,count+word.size()); for(auto c:word) st.erase(c); } dfs(arr,index+1,st,count); } bool check1(string &word, unordered_set<char> st){ for(auto c:word){ if(st.count(c)) return false; st.insert(c); } return true; } };
