题目描述
给定一个字符串数组 arr
,字符串 s
是将 arr
某一子序列字符串连接所得的字符串,如果 s
中的每一个字符都只出现过一次,那么它就是一个可行解。
请返回所有可行解 s
中最长长度。
样例
输入:arr = ["un","iq","ue"]
输出:4
解释:所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique",最大长度为 4。
输入:arr = ["cha","r","act","ers"]
输出:6
解释:可能的解答有 "chaers" 和 "acters"。
输入:arr = ["abcdefghijklmnopqrstuvwxyz"]
输出:26
限制
1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i]
中只含有小写英文字母。
算法
(暴力枚举) $O(n2^n\cdot L)$
- 枚举每种字符串组合,判断选中的字符串中每个字符是否都只出现了一次。如果是,则更新答案。
时间复杂度
- 枚举每种字符串组合需要 $O(n 2^n)$ 的时间复杂度,判断字符需要 $O(L)$ 的时间复杂度。
- 故总时间复杂度为 $O(n2^n \cdot L)$。
空间复杂度
- 判断每个字符都只出现了一次可以用位运算,故空间复杂度为 $O(1)$。
C++ 代码
class Solution {
public:
int maxLength(vector<string>& arr) {
int n = arr.size();
int ans = 0;
for (int s = 1; s < (1 << n); s++) {
int v = 0;
bool flag = true;
for (int i = 0; i < n; i++)
if ((s >> i) & 1) {
for (char c : arr[i]) {
if ((v >> (c - 'a')) & 1) {
flag = false;
break;
}
v |= 1 << (c - 'a');
}
if (!flag) break;
}
if (flag) {
int t = 0;
for (; v; v -= v & -v)
t++;
ans = max(ans, t);
}
}
return ans;
}
};
for (; v; v -= v & -v)
t++;
请问一下这里是怎么求出字符串的个数的
这个循环是统计
v
的二进制表示中 1 的个数,采用了lowbit
的算法谢谢大佬!