Skip to content

Commit 90e3266

Browse files
maolonglongmaolonglong
committed
feat: add solutions to lc problem: No.1239
1 parent b01b916 commit 90e3266

File tree

5 files changed

+276
-3
lines changed

5 files changed

+276
-3
lines changed

‎solution/1200-1299/1239.Maximum Length of a Concatenated String with Unique Characters/README.md

Lines changed: 94 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -42,27 +42,119 @@
4242
<li><code>arr[i]</code>&nbsp;中只含有小写英文字母</li>
4343
</ul>
4444

45-
4645
## 解法
4746

4847
<!-- 这里可写通用的实现逻辑 -->
4948

49+
状态压缩，用一个 32 位数记录字母的出现情况，`masks` 存储之前枚举的字符串。
50+
5051
<!-- tabs:start -->
5152

5253
### **Python3**
5354

5455
<!-- 这里可写当前语言的特殊实现逻辑 -->
5556

5657
```python
57-
58+
class Solution:
59+
def maxLength(self, arr: List[str]) -> int:
60+
def ones_count(x):
61+
c = 0
62+
while x:
63+
x &= x - 1
64+
c += 1
65+
return c
66+
67+
ans = 0
68+
masks = [0]
69+
for s in arr:
70+
mask = 0
71+
for ch in s:
72+
ch = ord(ch) - ord('a')
73+
if (mask >> ch) & 1 == 1:
74+
mask = 0
75+
break
76+
mask |= 1 << ch
77+
if mask == 0:
78+
continue
79+
for m in masks:
80+
if m & mask == 0:
81+
masks.append(m | mask)
82+
ans = max(ans, ones_count(m | mask))
83+
84+
return ans
5885
```
5986

6087
### **Java**
6188

6289
<!-- 这里可写当前语言的特殊实现逻辑 -->
6390

6491
```java
92+
class Solution {
93+
public int maxLength(List<String> arr) {
94+
int ans = 0;
95+
List<Integer> masks = new ArrayList<>();
96+
masks.add(0);
97+
98+
loop:
99+
for (String s : arr) {
100+
int mask = 0;
101+
for (char ch : s.toCharArray()) {
102+
ch -= 'a';
103+
if (((mask >> ch) & 1) == 1) {
104+
continue loop;
105+
}
106+
mask |= 1 << ch;
107+
}
108+
int n = masks.size();
109+
for (int i = 0; i < n; i++) {
110+
int m = masks.get(i);
111+
if ((m & mask) == 0) {
112+
masks.add(m | mask);
113+
ans = Math.max(ans, Integer.bitCount(m | mask));
114+
}
115+
}
116+
}
117+
118+
return ans;
119+
}
120+
}
121+
```
65122

123+
### **Go**
124+
125+
```go
126+
func maxLength(arr []string) int {
127+
128+
max := func(x, y int) int {
129+
if x > y {
130+
return x
131+
}
132+
return y
133+
}
134+
135+
ans := 0
136+
masks := []int{0}
137+
138+
loop:
139+
for _, s := range arr {
140+
mask := 0
141+
for _, ch := range s {
142+
ch -= 'a'
143+
if (mask>>ch)&1 == 1 {
144+
continue loop
145+
}
146+
mask |= 1 << ch
147+
}
148+
for _, m := range masks {
149+
if m&mask == 0 {
150+
masks = append(masks, m|mask)
151+
ans = max(ans, bits.OnesCount(uint(m|mask)))
152+
}
153+
}
154+
}
155+
156+
return ans
157+
}
66158
```
67159

68160
### **...**

‎solution/1200-1299/1239.Maximum Length of a Concatenated String with Unique Characters/README_EN.md

Lines changed: 94 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -45,18 +45,111 @@ Maximum length is 4.
4545

4646
## Solutions
4747

48+
State compression uses a 32-bit number to record the appearance of letters, and `masks` stores the previously enumerated strings.
49+
4850
<!-- tabs:start -->
4951

5052
### **Python3**
5153

5254
```python
53-
55+
class Solution:
56+
def maxLength(self, arr: List[str]) -> int:
57+
def ones_count(x):
58+
c = 0
59+
while x:
60+
x &= x - 1
61+
c += 1
62+
return c
63+
64+
ans = 0
65+
masks = [0]
66+
for s in arr:
67+
mask = 0
68+
for ch in s:
69+
ch = ord(ch) - ord('a')
70+
if (mask >> ch) & 1 == 1:
71+
mask = 0
72+
break
73+
mask |= 1 << ch
74+
if mask == 0:
75+
continue
76+
for m in masks:
77+
if m & mask == 0:
78+
masks.append(m | mask)
79+
ans = max(ans, ones_count(m | mask))
80+
81+
return ans
5482
```
5583

5684
### **Java**
5785

5886
```java
87+
class Solution {
88+
public int maxLength(List<String> arr) {
89+
int ans = 0;
90+
List<Integer> masks = new ArrayList<>();
91+
masks.add(0);
92+
93+
loop:
94+
for (String s : arr) {
95+
int mask = 0;
96+
for (char ch : s.toCharArray()) {
97+
ch -= 'a';
98+
if (((mask >> ch) & 1) == 1) {
99+
continue loop;
100+
}
101+
mask |= 1 << ch;
102+
}
103+
int n = masks.size();
104+
for (int i = 0; i < n; i++) {
105+
int m = masks.get(i);
106+
if ((m & mask) == 0) {
107+
masks.add(m | mask);
108+
ans = Math.max(ans, Integer.bitCount(m | mask));
109+
}
110+
}
111+
}
112+
113+
return ans;
114+
}
115+
}
116+
```
59117

118+
### **Go**
119+
120+
```go
121+
func maxLength(arr []string) int {
122+
123+
max := func(x, y int) int {
124+
if x > y {
125+
return x
126+
}
127+
return y
128+
}
129+
130+
ans := 0
131+
masks := []int{0}
132+
133+
loop:
134+
for _, s := range arr {
135+
mask := 0
136+
for _, ch := range s {
137+
ch -= 'a'
138+
if (mask>>ch)&1 == 1 {
139+
continue loop
140+
}
141+
mask |= 1 << ch
142+
}
143+
for _, m := range masks {
144+
if m&mask == 0 {
145+
masks = append(masks, m|mask)
146+
ans = max(ans, bits.OnesCount(uint(m|mask)))
147+
}
148+
}
149+
}
150+
151+
return ans
152+
}
60153
```
61154

62155
### **...**

‎solution/1200-1299/1239.Maximum Length of a Concatenated String with Unique Characters/Solution.go

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
func maxLength(arr []string) int {
2+
3+
max := func(x, y int) int {
4+
if x > y {
5+
return x
6+
}
7+
return y
8+
}
9+
10+
ans := 0
11+
masks := []int{0}
12+
13+
loop:
14+
for _, s := range arr {
15+
mask := 0
16+
for _, ch := range s {
17+
ch -= 'a'
18+
if (mask>>ch)&1 == 1 {
19+
continue loop
20+
}
21+
mask |= 1 << ch
22+
}
23+
for _, m := range masks {
24+
if m&mask == 0 {
25+
masks = append(masks, m|mask)
26+
ans = max(ans, bits.OnesCount(uint(m|mask)))
27+
}
28+
}
29+
}
30+
31+
return ans
32+
}

‎solution/1200-1299/1239.Maximum Length of a Concatenated String with Unique Characters/Solution.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
class Solution {
2+
public int maxLength(List<String> arr) {
3+
int ans = 0;
4+
List<Integer> masks = new ArrayList<>();
5+
masks.add(0);
6+
7+
loop:
8+
for (String s : arr) {
9+
int mask = 0;
10+
for (char ch : s.toCharArray()) {
11+
ch -= 'a';
12+
if (((mask >> ch) & 1) == 1) {
13+
continue loop;
14+
}
15+
mask |= 1 << ch;
16+
}
17+
int n = masks.size();
18+
for (int i = 0; i < n; i++) {
19+
int m = masks.get(i);
20+
if ((m & mask) == 0) {
21+
masks.add(m | mask);
22+
ans = Math.max(ans, Integer.bitCount(m | mask));
23+
}
24+
}
25+
}
26+
27+
return ans;
28+
}
29+
}

‎solution/1200-1299/1239.Maximum Length of a Concatenated String with Unique Characters/Solution.py

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
class Solution:
2+
def maxLength(self, arr: List[str]) -> int:
3+
def ones_count(x):
4+
c = 0
5+
while x:
6+
x &= x - 1
7+
c += 1
8+
return c
9+
10+
ans = 0
11+
masks = [0]
12+
for s in arr:
13+
mask = 0
14+
for ch in s:
15+
ch = ord(ch) - ord('a')
16+
if (mask >> ch) & 1 == 1:
17+
mask = 0
18+
break
19+
mask |= 1 << ch
20+
if mask == 0:
21+
continue
22+
for m in masks:
23+
if m & mask == 0:
24+
masks.append(m | mask)
25+
ans = max(ans, ones_count(m | mask))
26+
27+
return ans

0 commit comments

Comments
 (0)