# 135 ms Python solution with bit manipulation

• Its easy to use binary to enumerate which char we will keep.
• The key to speed up is I record all same locations, and store the number to maps[].
• So, if binary number map[i] & x == x(x is the binary representation while enumerating), this means we have a word in dictionary which will have same abbr.
``````class Solution(object):
def minAbbreviation(self, target, dictionary):
"""
:type target: str
:type dictionary: List[str]
:rtype: str
"""
dictionary = [i for i in dictionary if len(i) == len(target)]
if not dictionary:
return str(len(target))

# calculate the value to represent same locations
maps = []
for i in dictionary:
for j in xrange(len(target)):
if target[j] == i[j]:
mask |= (1 << j)

res = target
for i in xrange(1 << len(target)):
for j in maps:
# This means same abbr
if i & j == i:
break

# this is just to construct the abbr
else:
pre = 0
tmpstr = ""
for j in xrange(len(target)):
if i & (1 << j):
if pre < j:
tmpstr += str(j - pre)
tmpstr += target[j]
pre = j + 1
if pre < len(target):
tmpstr += str(len(target) - pre)
if len(tmpstr) < len(res):
res = tmpstr
return res

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.