LeetCode 1239. 串联字符串的最大长度【递归&位运算】

分手后的思念是犯贱 2022-10-23 08:01 127阅读 0赞

> 二分递归  
> 使用位运算去判断  
> 可以不可以继续装下一个字符串更快一点

#define debug(x) cout<<#x<<": "<<x<<endl;
    
    class Solution { 
    public:
        vector<int> barr;
        vector<string> arr;
        int ret=-1;
        int maxLength(vector<string>& arr) { 
            barr = vector<int>(arr.size(),0);
            this->arr = arr;
            for(int j=0;j<arr.size();j++){ 
                for(int i=0;i<arr[j].size();i++){ 
                    if( (barr[j] & (1<<( arr[j][i]-'a'))) ){ 
                        barr[j] = -1;
                        break;
                    }
                    barr[j] |= 1<<( arr[j][i]-'a');
                }
            }
            
            for(int i=this->barr.size()-1;i >= 0;i--){ 
                if(this->barr[i]==-1){ 
                    this->arr.erase(this->arr.begin()+i);
                    this->barr.erase(this->barr.begin()+i);
                }    
            }
            
            findw(0,0,0);
            return ret;
        }
        
        bool findw(int p,int b,int tret){ 
            if( p==barr.size() ){ 
                ret = max(ret,tret);
                return true;
            }
            
            if( (b&barr[p]) == 0){ 
                findw(p+1,b|barr[p],tret+arr[p].size());
            }
            findw(p+1,b,tret);
            return true;
        }
    };

![在这里插入图片描述][20210309144950586.png]

[20210309144950586.png]: /images/20221023/a75e7b6a2e344d528d16cd278bd8ef9a.png