leetcode1239 串联字符串的最大长度

题目

串联字符串的最大长度

分析

如果这题说的是子串，那么这题解法就是滑动窗口，但是这题说的是子序列，那么先暴力搜索一把再说，真男人就该暴力搜索。

写个check方法，再dfs即可。

代码

class Solution {
private:
    int res;

    bool check(string& str) {
        vector<char> vec(26, 0);
        for (auto & ch : str) {
            if (vec[ch - 'a'] != 0) {
                return false;
            }
            vec[ch - 'a'] = 1;
        }
        return true;
    }

    void dfs(string cur, int k, vector<string>& arr) {
        res = max((int)cur.size(), res);

        for (int i = k; i < arr.size(); i++) {
            string str = cur + arr[i];
            if (check(str)) {
                dfs(str, i + 1, arr);
            }
        }
    }
public:
    int maxLength(vector<string>& arr) {
        res = 0;    
        dfs("", 0, arr);

        return res;
    }
};