資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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 大小的最大值
- 如果 ok(v[j], arr[i]) 為真，則
- 返回 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 次檢視
廣告