文章目录
- 题目
- 代码(9.29 首刷部分看解析)
题目
Leetcode 1239. 串联字符串的最大长度
代码(9.29 首刷部分看解析)
class Solution {
public:unordered_set<int> skip;unordered_set<char> used;int maxLength(vector<string>& arr) {for(int i = 0; i < arr.size(); ++i) {used.clear();for(char& c : arr[i]) {if(used.count(c)) {skip.insert(i);break;}used.insert(c);}}used.clear();return dfs(0, arr);}int dfs(int i, vector<string>& arr) {if(skip.count(i)) {return dfs(i+1, arr);}if(i == arr.size())return 0;for(char& c : arr[i]) {if(used.count(c)) return dfs(i+1, arr);}for(char& c : arr[i])used.insert(c);int use = arr[i].size() + dfs(i+1, arr);for(char& c : arr[i]) // 回溯used.erase(c);int not_use = dfs(i+1, arr);return max(not_use, use);}
};