-
Notifications
You must be signed in to change notification settings - Fork 1.6k
/
maximum-hamming-distances.py
51 lines (48 loc) · 1.26 KB
/
maximum-hamming-distances.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# Time: O(m * 2^m)
# Space: O(2^m)
# bitmasks, knapsack dp
class Solution(object):
def maxHammingDistances(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: List[int]
"""
dp = [float("-inf")]*(1<<m)
for x in nums:
dp[x] = 0
for i in xrange(m):
new_dp = dp[:]
for mask in xrange(1<<m):
new_dp[mask] = max(new_dp[mask], dp[mask^(1<<i)]+1)
dp = new_dp
return [dp[x] for x in nums]
# Time: O(m * 2^m)
# Space: O(2^m)
# bitmasks, bfs
class Solution2(object):
def maxHammingDistances(self, nums, m):
"""
:type nums: List[int]
:type m: int
:rtype: List[int]
"""
q = []
dist = [-1]*(1<<m)
for x in nums:
if dist[x] != -1:
continue
dist[x] = 0
q.append(x)
d = 0
while q:
d += 1
new_q = []
for u in q:
for i in xrange(m):
if dist[u^(1<<i)] != -1:
continue
dist[u^(1<<i)] = d
new_q.append(u^(1<<i))
q = new_q
return [m-dist[((1<<m)-1)^x] for x in nums]