最短独占单词缩写

该题解使用位掩码来枚举target字符串的所有可能的缩写形式。对于字典中的每个单词，计算它与target的位掩码差异，并将差异掩码存储在一个集合中。然后枚举target的所有可能的位掩码，检查每个掩码是否能够区分target和字典中的所有单词。在所有有效的掩码中，选择对应的缩写长度最短的那个作为最终答案。

时间复杂度: O(mn + m2^n)

空间复杂度: O(m + n)

class Solution:
    def minAbbreviation(self, target: str, dictionary: List[str]) -> str:
        ans = None
        mmin = None

        def getAbbr(mask, target):
            ans = ''
            num = 0
            prev = None
            for i in range(len(target)):
                if mask & (1 << i):
                    if prev != None:
                        ans += str(i - prev)
                        num += 1
                        prev = None
                    ans += target[i]
                    num += 1
                else:
                    if prev == None:
                        prev = i
            if prev:
                ans += str(len(target) - prev)
                num += 1
            return ans, num

        # 生成字典中单词的差异掩码
        masks = set()
        for word in dictionary:
            if len(target) == len(word):
                mask = 0
                for i in range(len(target)):
                    if target[i] != word[i]:
                        mask += (1 << i)
                masks.add(mask)
        
        # 如果字典为空，直接返回target的长度作为缩写
        if len(masks) == 0:
            return str(len(target))
        
        # 枚举target的所有可能的位掩码
        for i in range(2 ** len(target)):
            # 检查当前掩码是否能够区分target和字典中的所有单词
            if all(i & mask > 0 for mask in masks):
                abbr, length = getAbbr(i, target)
                if ans == None or length < mmin:
                    ans = abbr
                    mmin = length
        return ans