Leetcode 1239. 串联字符串的最大长度

题目

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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37