Day136 | 灵神 | 回溯算法 | 子集型 串联字符串的最大长度

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

1239. 串联字符串的最大长度 - 力扣（LeetCode）

笔者这道题写的感觉很麻烦，大家可以去看看官方题解

思路：

用选或不选这个思路，会让思路变得非常简单。具体来说就是看选不选当前的字符串，选的话长度加上当前字符串，不选的话就递归下一个字符串选或不选

难点在于 我们决定要选当前字符串的情况下，我们能不能选当前字符串，即看这个字符串和已经选了的有没有重复，除此之外还要看组内有没有重复的

用下面这个函数来检查能不能选当前字符串

遍历字符串，如果在之前选的里面没出现过，对应字符++，如果有字符出现过，那代表我们都将不能选这个字符串，所以直接break

for循环结束后，有两种情况，第一种就是i==s.size()这说明我们这个字符串可以选，因为遍历到了最后都没有重复（注意，之后恢复 现场的时候要把hash值给减回去）

下面就是字符串不能选的情况，因为hash数组是全局变量，所以还得给它加了的给减回去，所以才有下面的for循环

bool choice(string &s)
   {
       int i=0;
       for(i=0;i<s.size();i++)
       {
           if(hash[s[i]-'a']==0)
               hash[s[i]-'a']++;
           else
               break;
       }
       if(i==s.size())
           return true;
       for(int j=0;j<i;j++)
           if(hash[s[j]-'a']!=0)
               hash[s[j]-'a']--;
       return false;
   }

完整代码：

class Solution {
public:
    int res=0;
    int hash[26]={0};
    //检查是不是可以选当前字符串
    bool choice(string &s)
    {
        int i=0;
        for(i=0;i<s.size();i++)
        {
            if(hash[s[i]-'a']==0)
                hash[s[i]-'a']++;
            else
                break;
        }
        if(i==s.size())
            return true;
        for(int j=0;j<i;j++)
            if(hash[s[j]-'a']!=0)
                hash[s[j]-'a']--;
        return false;
    }
    void dfs(vector<string>& arr,int i,int length)
    {
        if(i>=arr.size())
        {
            res=max(res,length);
            return ;
        }
        //选
        if(choice(arr[i]))
        {
            length+=arr[i].size();
            dfs(arr,i+1,length);
            length-=arr[i].size();
            //当choice是true的时候，我们把对应字符都给加了一遍，恢复现场的时候要减回来
            for(auto c:arr[i])
                hash[c-'a']--;
        }
        //不选
        dfs(arr,i+1,length);
    }
    int maxLength(vector<string>& arr) {
        dfs(arr,0,0);
        return res;
    }
};