1414
1515public class LeetCode1239 {
1616public static void main (String []args ) {
17- Solution solution =new Solution1 ();
17+ Solution solution =new Solution2 ();
1818List <String >testCase =new ArrayList <>(Arrays .asList ("un" ,"iq" ,"ue" ));
1919System .out .println (solution .maxLength (testCase ));
2020 }
@@ -59,6 +59,7 @@ public void dfs(List<Integer> masks, int pos, int mask) {
5959class Solution1 extends Solution {
6060@ Override
6161public int maxLength (List <String >arr ) {
62+ // 使用哈希集合去重
6263List <HashSet <Character >>all =new ArrayList <>();
6364all .add (new HashSet <>());
6465int ans =0 ;
@@ -80,3 +81,37 @@ public int maxLength(List<String> arr) {
8081return ans ;
8182 }
8283}
84+
85+ class Solution2 extends Solution {
86+ @ Override
87+ public int maxLength (List <String >arr ) {
88+ int ans =0 ;
89+ List <Integer >masks =new ArrayList <>();
90+ masks .add (0 );// 空串
91+
92+ for (String s :arr ) {
93+ // 1. 判断字符串中有没有重复的字符
94+ int mask =0 ;
95+ for (Character c :s .toCharArray ()) {
96+ int ch =c -'a' ;
97+ if ((mask &1 <<ch ) !=0 ) {
98+ mask =0 ;
99+ break ;
100+ }
101+ // 没有重复字符，当前字符串就是可行解的一种
102+ mask |=1 <<ch ;
103+ }
104+ // 有重复字符，直接跳过
105+ if (mask ==0 )continue ;
106+ // 2. 和前i项可行解做拼接，判断是否满足条件
107+ for (int i =0 ;i <masks .size ();i ++) {
108+ if ((mask &masks .get (i )) ==0 ) {
109+ // 和空串拼接，就是将当前串添加到可行解中
110+ masks .add (mask |masks .get (i ));
111+ ans =Math .max (ans ,Integer .bitCount (mask |masks .get (i )));
112+ }
113+ }
114+ }
115+ return ans ;
116+ }
117+ }