C++ 中具有唯一字符的连接字符串的最大长度

假设我们有一个字符串数组 arr。字符串 s 是 arr 的一个子序列的连接，并且具有唯一的字符。找到 s 的最大可能长度。如果输入类似于 [“cha”, “r”, “act”, “ers”]，则输出将为 6，可能的解决方案为“chaers”和“acters”。

为了解决这个问题，我们将遵循以下步骤：

  • 创建一个名为 ok() 的方法，它将接收字符串 s 和 t 作为参数。它将执行以下操作：
  • 创建一个映射 x
  • 对于范围从 0 到 s 大小的 i
    • 将 x[s[i]] 加 1
    • 如果 x[s[i]] > 1，则返回 false
  • 对于范围从 0 到 t 大小的 i
    • 将 x[t[i]] 加 1
    • 如果 x[t[i]] > 1，则返回 false
  • 返回 true
  • 实际方法将如下所示：
  • 创建一个名为 v 的字符串数组，并将 ans := 0，并将一个空字符串插入 v 中。
  • 对于范围从 0 到 arr 大小的 i
    • n := v 的大小
    • 对于范围从 0 到 n – 1 的 j
      • 如果 ok(v[j], arr[i]) 为真，则
        • t := v[j] + arr[i]
        • 将 t 插入 v 中
        • ans := ans 和 t 大小的最大值
  • 返回 ans

让我们看看下面的实现以更好地理解：

示例

 实时演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool ok(string s, string t){
      map <char, int > x;
      for(int i = 0; i < s.size(); i++){
         x[s[i]]++;
         if(x[s[i]] >1)return false;
      }
      for(int i = 0; i < t.size(); i++){
         x[t[i]]++;
         if(x[t[i]]>1)return false;
      }
      return true;
   }
   int maxLength(vector<string>& arr) {
      vector <string> v;
      int ans = 0;
      v.push_back("");
      for(int i = 0; i < arr.size(); i++){
         int n = v.size();
         for(int j = 0; j < n; j++){
            if(ok(v[j],arr[i])){
               string t = v[j]+arr[i];
               v.push_back(t);
               ans = max(ans,(int)t.size());
            }
         }
      }
      return ans;
   }
};
main(){
   vector<string> v = {"cha","r","act","ers"};
   Solution ob;
   cout << (ob.maxLength(v));
}

输入

["cha","r","act","ers"]

输出

6

更新于： 2020年5月2日

371 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告