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

思路:

二进制化 + 二位搜索

代码:


class Solution {
queue<int> que;
public:
    int maxLength(vector<string>& arr) {
        int onehot , maxlen = 0;
        // 2^n算法
        for(string s : arr ) {
            int onehot;
            if(!w2i(s, onehot)) continue;
            que.push(onehot);
            int n = que.size();
            while(n--) {
                int v = que.front();
                que.pop();
                que.push(v);
                if((v & onehot) == 0) {
                    que.push(v | onehot);
                }
            }
        }

        while(que.size()) {
            int v = que.front();
            que.pop();
            maxlen = max(maxlen, onehotLen(v));
        
        }
        return maxlen;
    }

    int onehotLen(int v) {
        int t = 0; 
        while(v) {
            if(v & 1) ++t;
            v >>= 1;
             
        }
        return t;
    }


    bool w2i(string s, int &onehot) {
        set<char> setc;
        onehot = 0;
        for(auto c : s){
            if(setc.count(c) == 1) {
                return false;
            }else{
                onehot |= (1 << (c - 'a'));
                setc.insert(c);
            }
        }
        return true;
    }


};

Comments