题目描述
给定一个字符串数组 arr,字符串 s 是将 arr 某一子序列字符串连接所得的字符串,如果 s 中的每一个字符都只出现过一次,那么它就是一个可行解。
请返回所有可行解 s 中最长长度。
样例
示例 1:
输入:arr = ["un","iq","ue"]
输出:4
解释:所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique",最大长度为 4。
示例 2:
输入:arr = ["cha","r","act","ers"]
输出:6
解释:可能的解答有 "chaers" 和 "acters"。
示例 3:
输入:arr = ["abcdefghijklmnopqrstuvwxyz"]
输出:26
提示:
1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] 中只含有小写英文字母
算法1
1 使用DFS 遍历各种组合
2 为了检查两个字符串是否存在字母冲突 使用01位记录字母的出现与否
本题为了代码便于编写 使用26元素的数组记录字符是否出现
C++ 代码
class Solution {
public:
vector<int> currenthash;
int currentLen;
vector<vector<int>> hashVec;
int ret = -9999;
bool CheckHash(vector<int>& hash1, vector<int>& hash2) {
for (int i = 0; i < hash1.size(); i++) {
if (hash1[i] + hash2[i] > 1)
return false;
}
return true;
}
void startTry(int idx,int currentLen, vector<string>& arr)
{
if (idx == arr.size()) {
ret = max(ret, currentLen);
return;
}
if (CheckHash(currenthash, hashVec[idx])) {
currentLen += arr[idx].size();
for (int i = 0; i < currenthash.size(); i++) {
currenthash[i] += hashVec[idx][i];
}
startTry(idx + 1, currentLen,arr);
for (int i = 0; i < currenthash.size(); i++) {
currenthash[i] -= hashVec[idx][i];
}
currentLen -= arr[idx].size();
}
startTry(idx + 1, currentLen, arr);
}
int maxLength(vector<string>& arr) {
currenthash = vector<int>(26, 0);
currentLen = 0;
hashVec = vector<vector<int>>(arr.size(), vector<int>(26, 0));
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < arr[i].size(); j++) {
int idx = arr[i][j] - 'a';
hashVec[i][idx]++;
//优化
}
}
currenthash = vector<int>(26, 0);
currentLen = 0;
startTry(0, 0,arr);
return ret;
}
};