题目描述

由于题目答案与字符的顺序无关，那么可以依次枚举是否选用当前的字符串，分为选与不选两种情况。
用dfs+回溯的方式搜索即可

C++ 代码

class Solution {
public:
    int cnt[26] = {};
    int res = 0;
    bool check(string x)
    {
        unordered_map<int, int>h;
        for (auto a : x) 
        {
            h[a - 'a'] ++;
            if (h[a - 'a'] > 1) return false;
        }
        return true;
    }

    bool check1(string start)
    {
        for (auto x :start)
        {
            if (cnt[x - 'a']) return false;
        }
        return true;
    }

    int maxLength(vector<string>& arr) {
        vector<string> tmp;
        for (auto x :arr)
        {
            if (check(x))
                tmp.push_back(x);
        }
        if (tmp.empty()) return 0; 

        string a = "";
        dfs(tmp, a, 0);
        return res;
    }

    void dfs(vector<string>& num, string &a, int start)
    {
        if (res < a.size()) res = a.size();
        if (start == num.size()) return;
        if (check1(num[start]))
        {
            a += num[start];
            for (auto x : num[start]) cnt[x - 'a'] ++;
            dfs(num, a, start + 1);
            for (auto x : num[start]) cnt[x - 'a'] --;
            a = a.substr(0, a.size() - num[start].size());
        }

        dfs(num, a, start + 1);
    }

};