Leetcode刷題學習筆記–Combination

1239. Maximum Length of a Concatenated String with Unique Characters(Medium)

給定一個字串列表，例如{"un","iq","ue"}，找出任意的組合中，但是字母不能重複的最長字串。這一題有兩個重點:

  1. 怎麼快速的比對兩個字串，有沒有重複的字母。
  2. 全部的字串組合。{"un","iq","ue","uniq","unue","ique","unique"}

第一個問題可以用bit manipulation把每個字母都成不同的bit。只要兩個字串的數字做AND就可以得知有沒有字母重複。兩個字串串接的話，只要把數字做OR即可。







int getIntVal(string s) {
    int rtn{0};
    for(auto& c : s)
        rtn |= 1 << (c - 'a');
    return rtn;
}

所有字串的組合。
如果只有一個字串{"un"}，那所有的組合只有兩種，自己和空集合{"","un"}。
如果有兩個字串{"un","iq"}，那就是把{"iq"}自己與之前的組合合併起來，就是{"iq"}{"","un"} = {"iq","iqun"}還包括原本的組合，所以新的組合是{"","un","iq","iqun"}。
同理如果是三個字串{"un","iq","ue"}，就是把{"ue"}與前兩個的組合{"","un","iq","iqun"}組成，{"","un","iq","iqun","ue","ueun","ueiq","ueiqun"}。

關於組合的程式碼如下:












int maxLength(vector<string>& arr) {
    auto n = arr.size();
    vector<string> wordlist;
    wordlist.push_back("");
    for(int i = 0; i < n; ++i) {
        // 只處理前面舊的字串，所以先取得size
        int len = wordlist.size(); 
        for(int j = 0; j < len; ++j)
            wordlist.push_back(arr[i] + wordlist[j]);
    }
}

再加上判斷是否字母重複，就可以得到以下的程式碼。





































class Solution {
    int getIntVal(string s) {
        int rtn{0};
        for(auto& c : s) {
            rtn |= 1 << (c - 'a');
        }
        
        return rtn;
    }
    
    vector<string> wordlist;
    vector<int> sym;
    
public:
    int maxLength(vector<string>& arr) {
        auto n = arr.size();
        wordlist.push_back("");
        sym.push_back(0);
        int maxcnt = 0;
        for(int i = 0; i < n; ++i) {
            set<char> s(arr[i].begin(), arr[i].end());
            if(s.size() != arr[i].length()) continue;
            int len = wordlist.size();
            int si = getIntVal(arr[i]);
            for(int j = 0; j < len; ++j) {
                if((si & sym[j]) == 0) {
                    maxcnt = max(maxcnt, (int)(wordlist[j].length() + arr[i].length()));
                    wordlist.push_back(arr[i] + wordlist[j]);
                    sym.push_back(si | sym[j]);
                }
            }
        }
        
        return maxcnt;
    }
};
tags: leetcode 刷題
Select a repo