Python DFS Solution with Bit Manipulation


  • 4

    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 '')
    

  • 0

    @在线疯狂 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!


  • 0

    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)) ?


Log in to reply
 

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