LeetCode 1239 Maximum Length of a Concatenated String with Unique Characters

題目連結

---

❗️ 題意

給定一個字串陣列 $arr$，請你從裡面取出一些字串並將其連接起來，要保證不能出現重複的字元，請輸出所有可能的結果中長度最長為何?

• Input: $arr = $ [“un”, “iq”,“ue”]

• Output: $4$

  • “ ”, “un”, “iq”, “ue”, “uniq”, “ique”
  • 長度最長的為 “uniq” 與 “ique”，兩者皆為4

• Constraints:

  • $1 \leq arr.length \leq 16$
  • $1 \leq arr[i].length \leq 26$
    • $arr[i]$ contains only lowercase English letters.

---

✔️ 題解

對於此題，由於其陣列長度與其中的字串長度皆不大，因此我們可以很直覺的想到或許可以透過枚舉的方式來解決，因此我在一開始是使用bitmask來枚舉，假設我們現在有一個長度是4的陣列，而bitmask現在是1011，就代表我們要拿第一個，第三個，第四個來計算其連接起來後的結果，而我們只需要透過枚舉0000 ~ 1111，也就是16(1<<4)種情況，就可以將所有可能的情況皆枚舉出來，這種做法由於是將所有可能皆嘗試一次，因此只適用於輸入的陣列不要太大的情況，以此題來說陣列大小最大只有16而已，因此此做法是可以成功AC的，但其效率並不好。

因此我們可以進一步思考，其實很多結果根本不需要嘗試，假設1100就已經違反規定，那其他的例如1101, 1110, 1111根本沒有試的必要，因此我們可以使用 Backtracking 的方式，只對還沒有違反規定的結果來去枚舉下一步，透過這種剪枝的方式，就能大幅度的減少所需要枚舉的次數。

---

💻 程式碼

• Bit Mask

  // 570 ms, AC
  class Solution {
  public:
      vector<string>now;
      int used[30];
      int ans;
      int check(){
          bool alpha[30] = {0};
          int tot = 0;
          for(auto st: now){
              for(auto s: st){
                  if(alpha[s - 'a'] == true){
                      return -1;
                  }
                  alpha[s - 'a'] = true;
                  tot++;
              }
          }
          return tot;
      }
      int maxLength(vector<string>& arr) {
          for(int i = 0; i < (1 << arr.size()); i++){
              now.clear();
              for(int j = 0; j < arr.size(); j++){
                  if((i >> j) & 1){
                      now.emplace_back(arr[j]);
                  }
              }
              ans = max(ans, check());
          }
          return ans;
      }
  };

• Backtracking

  // 21ms, AC
  class Solution {
  public:
      vector<string>now;
      int used[30];
      int ans;
      int check(){
          bool alpha[30] = {0};
          int tot = 0;
          for(auto st: now){
              for(auto s: st){
                  if(alpha[s - 'a'] == true){
                      return -1;
                  }
                  alpha[s - 'a'] = true;
                  tot++;
              }
          }
          return tot;
      }
      void dfs(int idx, vector<string>& arr){
          for(int i = idx + 1; i < arr.size(); i++){
              if(!used[i]){
                  now.emplace_back(arr[i]);
                  int chk = check();
                  if(chk != -1){
                      used[i] = true;
                      ans = max(ans, chk);
                      dfs(i, arr);
                  }
                  now.pop_back();
                  used[i] = false;
              }
          }
      }
      
      int maxLength(vector<string>& arr) {
          dfs(-1, arr);
          return ans;
      }
  };

  Runtime: 21 ms, faster than 72.91% of C++ online submissions

---

🧠 心得

我覺得的我的 check function並沒有寫好， 因為我每次計算時都要重新計算一次長度，但其實不需要這樣做，我們可以維護一組global的陣列，存著目前已使用的字元(a~z)，之後計算時只要針對目前要加入的字串去增加或減少此陣列即可，但我好懶就沒有改了XD

---