Leetcode.1239 串联字符串的最大长度
题目链接
Leetcode.1239 串联字符串的最大长度 Rating : 1720
题目描述
给定一个字符串数组 arr
,字符串 s
是将 arr
的含有 不同字母 的 子序列 字符串 连接 所得的字符串。
请返回所有可行解 s
中最长长度。
子序列 是一种可以从另一个数组派生而来的数组,通过删除某些元素或不删除元素而不改变其余元素的顺序。
示例 1:
输入:arr = [“un”,“iq”,“ue”]
输出:4
解释:所有可能的串联组合是:
“”
“un”
“iq”
“ue”
“uniq” (“un” + “iq”)
“ique” (“iq” + “ue”) 最大长度为 4。
示例 2:
输入:arr = [“cha”,“r”,“act”,“ers”]
输出:6
解释:可能的解答有 “chaers” 和 “acters”。
示例 3:
输入:arr = [“abcdefghijklmnopqrstuvwxyz”]
输出:26
提示:
- 1 < = a r r . l e n g t h < = 16 1 <= arr.length <= 16 1<=arr.length<=16
- 1 < = a r r [ i ] . l e n g t h < = 26 1 <= arr[i].length <= 26 1<=arr[i].length<=26
arr[i]
中只含有小写英文字母
分析:
我们先对 arr
做预处理,去掉有重复字母的字符串。对于每一个不含重复字母的字符串 s
,用一个二进制数表示它。例如:ab -> 3(011) , abc -> 7(111)
。将这样的二进制数存入一个新的列表 a
中。
用一个 二进制数mask
(
0
<
=
m
a
s
k
<
=
2
a
.
s
i
z
e
(
)
0 <= mask <= 2^{a.size()}
0<=mask<=2a.size()),表示选择a
中的的字符串情况。
用一个 len
来记录已经选择过的字符串的字母。
- 如果
len & a[j] != 0
,说明之前选过的字符串 有与 当前字符串a[j]
重复的字符,就跳过本轮循环。 - 如果
len & a[j] == 0
,说明之前选过的字符串 没有与 当前字符串a[j]
重复的字符,len
就记录上a[j]
的字母。
len
二进制 1
的个数就是本轮选择子串能拼接的最大长度。
时间复杂度: O ( m + n ∗ 2 n ) O(m+n * 2^n) O(m+n∗2n) m m m 为所有子串加起来的总长度
C++代码:
class Solution {
public:
int maxLength(vector<string>& arr) {
int ans = 0;
vector<int> a;
for(auto s:arr){
int mask = 0;
for(auto c:s){
int k = c - 'a';
if((mask >> k) & 1){
mask = 0;
break;
}
mask |= 1 << k;
}
if(mask) a.push_back(mask);
}
int n = a.size();
for(int mask = 1;mask < (1 << n);mask++){
int len = 0;
for(int j = 0;j < n;j++){
if((mask >> j) & 1){
if((len & a[j]) != 0) continue;
len |= a[j];
}
}
ans = max(ans,__builtin_popcount(len));
}
return ans;
}
};
Java代码:
class Solution {
public int maxLength(List<String> arr) {
List<Integer> a = new ArrayList<>();
for(var s:arr){
int mask = 0;
for(var c:s.toCharArray()){
int k = c - 'a';
if(((mask >> k) & 1) == 1){
mask = 0;
break;
}
mask |= (1 << k);
}
if(mask > 0) a.add(mask);
}
int n = a.size();
int ans = 0;
for(int mask = 1;mask < (1 << n);mask++){
int len = 0;
for(int j = 0;j < n;j++){
if(((mask >> j) & 1) == 1){
if((len & a.get(j)) != 0) continue;
len |= a.get(j);
}
}
ans = Math.max(ans,Integer.bitCount(len));
}
return ans;
}
}
相关文章
- 求一个字符串中子串连续出现的最大次数
- Lintcode--006(交叉字符串)
- python的字符串内建函数
- 一句python,一句R︱python中的字符串操作、中文乱码、NaN情况
- 获取uuid中的字符串,UUID('') is not JSON serializable解决方法,删除uuid中字符串的-
- LeetCode-944. 删列造序【数组,字符串】
- Leetcode537:复数乘法(medium, 字符串处理)
- 计算两个字符串最大公有子串
- ZZNUOJ_用C语言编写程序实现1176:查找最大字符串(指针专题)(附完整源码)
- 对称就是最大的美学,现有一道关于对称字符串的美学。已知: - 第1个字符串:R - 第2个字符串:BR - 第3个字符串:RBBR - 第4个字符串:BRRBRBBR - 第5个
- 1593. 拆分字符串使唯一子字符串的数目最大
- .删除子字符串的最大得分-c语言贪心算法
- Leetcode 2264. 字符串中最大的 3 位相同数字(可以,已解决)
- Python编程:判断字符串中是否包含中文
- 【编程实践】Golang 字符串数组排序
- Python: translate()审查清理文本字符串
- java实现字符串匹配问题之求两个字符串的最大公共子串
- 使用get_json_object处理hive sql中的json字符串
- Java核心类库之(常用API、字符串类、集合类、泛型)