411. Minimum Unique Word Abbreviation

A string such as "word" contains the following abbreviations:

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Given a target string and a set of strings in a dictionary, find an abbreviation of this target string with the smallest possible length such that it does not conflict with abbreviations of the strings in the dictionary.

Each number or letter in the abbreviation is considered length = 1. For example, the abbreviation "a32bc" has length = 4.

Note:

• In the case of multiple answers as shown in the second example below, you may return any one of them.
• Assume length of target string = m, and dictionary size = n. You may assume that m ≤ 21, n ≤ 1000, and $\log_2$n + m ≤ 20.

Examples:

"apple", ["blade"] -> "a4" (because "5" or "4e" conflicts with "blade")

"apple", ["plain", "amber", "blade"] -> "1p3" (other valid answers include "ap3", "a3e", "2p2", "3le", "3l1").

Solution: Bit Op

class Solution(object):
    def minAbbreviation(self, target, dictionary):
        """
        :type target: str
        :type dictionary: List[str]
        :rtype: str
        """
        words = [self.to_number(target, word)
                 for word in dictionary
                 if len(word) == len(target)]

        if not words:
            return str(len(target))

        min_len = float('inf')
        min_abbr = self.to_number(target, target)
        for abbr, length in self.abbrs(min_abbr, len(target)):
            if length < min_len and self.valid_abbr(abbr, words):
                min_len = length
                min_abbr = abbr
        return self.to_word(target, min_abbr)

    def abbrs(self, word, size, zeros=0):
        if word == 0:
            yield word, size
        else:
            for abbr, length in self.abbrs(word >> 1, size, 0):
                yield (abbr << 1) + 1, length
            if zeros > 0:
                size -= 1
            for abbr, length in self.abbrs(word >> 1, size, zeros + 1):
                yield (abbr << 1) + 0, length

    def valid_abbr(self, abbr, words):
        return not any(abbr & word == abbr for word in words)

    def to_number(self, target, word):
        number = 0
        for left, right in zip(target, word):
            number += left == right
            number <<= 1
        return number

    def to_word(self, target, number):
        chars = []
        zeros = 0
        for char in reversed(target):
            if number & 1 == 1:
                if zeros > 0:
                    chars.append(str(zeros))
                    zeros = 0
                chars.append(char)
            else:
                zeros += 1
            number >>= 1
        if zeros > 0:
            chars.append(str(zeros))
        return ''.join(reversed(chars))

Lessons:

• All words in dictionary with different sizes can be ignored. Simply return the size of target.
• Change every word in dictionary to a (binary) number, based on the following rule:

  target:  apple
    word:  amble
  number:  10011
  

• Based on the same rule, we can also change every target's abbreviation into a number. So for a word like apple, we will have 32 abbreviations, from 00000 to 11111 (0 to 31).
• To find a valid abbreviation, we need abbr & word == abbr is false for every word in dictionary. False means there is at least one position in abbr that can match the position in target, while word can not. So 1 & 0 = 0 which changes the abbr number at that position.
• Lastly, we can use DFS to find the length of every abbreviation.

Related:

• 320. Generalized Abbreviation