# Python DFS Solution with Bit Manipulation

• Words in dictionary can be converted to numbers using bit manipulation.

For example, if target is apple, a dictionary word amble could be converted to a binary number bin(10011), by determining whether the letters in the same position between target and word are equal or not.

``````a p p l e
a m b l e
1 0 0 1 1
``````

Abbrviation can also be converted to binary number. The letters in abbr could be converted to binary one, and the digits could be converted to zeros.
For example, one of the abbriviations of word manipulation is m2ip6n, could be converted to binary number bin(100110000001)

``````m a n i p u l a t i o n
m  2  i p      6      n
1 0 0 1 1 0 0 0 0 0 0 1
``````

We can use bitwise and operator to test whether an abbreviation abbr matched some words in the dictionary. If abbr & word == abbr, then abbr matched word.

Python code:

``````class Solution(object):
def minAbbreviation(self, target, dictionary):
"""
:type target: str
:type dictionary: List[str]
:rtype: str
"""
self.size = len(target)
self.wlist = [self.toNumber(target, d) \
for d in dictionary \
if len(d) == self.size]
self.ans = (1 << self.size) - 1
self.length = self.size
self.dfs(0, 0, 0)
return self.toWord(self.ans)
def dfs(self, number, depth, length):
if length >= self.length: return
if depth == self.size:
if not any(number & w == number for w in self.wlist):
self.ans = number
self.length = length
return
self.dfs((number << 1) + 1, depth + 1, length + 1)
if length == 0 or number & 1:
for x in range(2, self.size - depth + 1):
self.dfs(number << x, depth + x, length + 1)
def toNumber(self, target, word):
ans = 0
for x in range(self.size):
ans <<= 1
ans += target[x] == word[x]
return ans
def toWord(self, number):
ans = ''
cnt = 0
for x in range(self.size):
if number & (1 << self.size - x - 1):
if cnt:
ans += str(cnt)
cnt = 0
ans += target[x]
else:
cnt += 1
return ans + str(cnt or '')
``````

• @在线疯狂 I really like this solution in that:

1. It pre-process dictionary into list of bit representations of words for efficient match checking
2. It prunes the DFS tree aggressively as the algorithm proceeds
3. It has clear logic separations e.g. toNumber() and toWrod()

Great job!

• Hi, Thanks for sharing this solution.

May I ask if the depth and length in `def dfs(self, number, depth, length):` means the index to handle in `target` and the `abbreviation` length, respectively?

If in that case, may I ask why length in `self.dfs(number << x, depth + x, length + 1)` is always increase 1, not `length + len(str(x))` ?

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