串联字符串的最大长度

Trace

6.19 每日一题

传送门：https://leetcode-cn.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/

Problem

给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。

请返回所有可行解 s 中最长长度。

示例 1：

1
2
3

输入：arr = ["un","iq","ue"]
输出：4
解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。

示例 2：

1
2
3

输入：arr = ["cha","r","act","ers"]
输出：6
解释：可能的解答有 "chaers" 和 "acters"。

示例 3：

1 2	输入：arr = ["abcdefghijklmnopqrstuvwxyz"] 输出：26

数据范围：

1
2
3

1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] 中只含有小写英文字母

思路

arr.length <= 16，可以dfs。

最近能dfs就dfs，多练习下，之前总是因为写的太丑TLE。

class Solution {
public:
    unordered_map<char,int> mp;
    int Max=0;
    //考虑到第k个字符串；当前连接得的字符串的长度；字符串数组arr
    void dfs(int k,int len,vector<string>& arr){
        if(k==arr.size()){
            return ;
        }
        bool flag=true;
        // 一个string如果自己有重复元素，直接跳过
        unordered_map<char,int> mp2;
        for(int i=0;i<arr[k].size();i++){
            mp2[arr[k][i]]++;
            if(mp2[arr[k][i]]>=2){
                flag=false;
            }
        }
        // 存在一个字符，之前已经出现过，当前字符串就不能选
        for(int i=0;i<arr[k].size();i++){
            if(mp[arr[k][i]]!=0){
                flag=false;
            }
        }
        // 可选
        if(flag){
            for(int i=0;i<arr[k].size();i++){
                mp[arr[k][i]]++;
            }
            len+=arr[k].size();
            Max=max(Max,len);
            dfs(k+1,len,arr);
            // 选
            for(int i=0;i<arr[k].size();i++){
                mp[arr[k][i]]--;
            }
            len-=arr[k].size();
            dfs(k+1,len,arr);
            // 不选（先还原状态）
        }
        else{
            dfs(k+1,len,arr);
        }
    }
    int maxLength(vector<string>& arr) {
        // dfs可以写
        dfs(0,0,arr);
        return Max;
    }
};

明天填坑剪枝优化。