题目如下:
解题思路:首先过滤掉arr中有重复字符的元素,接下来就可以采用BFS的方法进行计算了。怎么判断两个字符串是否有相同字符呢?我的方法是把字符串转成二进制的方式,a对应2^0,c对应2^2,z对应2^25。这样的话,每一个字符串都可以计算出一个特征值,判断两个字符串是否有相同字符,只有判断两个特征值与操作的结果是否为0即可。
代码如下:
class Solution(object):
def maxLength(self, arr):
"""
:type arr: List[str]
:rtype: int
"""
arr_val = []
for i in arr:
val = 0
if len(set(list(i))) != len(i):continue
for j in i:
val |= 2**(ord(j) - ord('a'))
arr_val.append(val)
#print arr_val
queue = []
if len(arr_val) == 0:return 0
for (inx,val) in enumerate(arr_val):
queue.append((inx,val))
res = 0
while len(queue) > 0:
inx,val = queue.pop(0)
end = True
for i in range(inx+1,len(arr_val)):
if val & arr_val[i] != 0:continue
queue.append((i,val | arr_val[i]))
end = False
if end :
res = max(res,bin(val).count(''))
return res