Leetcode 0411. Minimum Unique Word Abbreviation

Problem statement

https://leetcode.com/problems/minimum-unique-word-abbreviation/

Solution

Let us for each word in dictionary and target evaluate forbidden masks: for example if target = "apple" and word = "oppra", then we have $01100$ mask, which is forbidden, it means we can not take $00000, 01000, 00100, 01100$, which are $1p3, 2p2, 1pp2$. Then we iterate over all possible $2^m$ binary masks and check if it is forbidden for one of our $n$ words. Forbidden means \texttt{candidate | masks[j] == masks[j]}. If it is forbidden for at least one word, this candidate is bad and we go to the next one.

Also we need to do a bit prunning to make it pass: if we already found the shortest possible abbreviation with length len(str(m)), we break.

Complexity

Overall time complexity is $O(n\cdot 2^m)$ and space complexity is $O(n)$.

Code

class Solution:
    def minAbbreviation(self, target, dictionary):
        m = len(target)
        dct = [w for w in dictionary if len(w) == m]
        n = len(dct)
        
        best = target
        masks = [0]*n
        
        for it, word in enumerate(dct):
            masks[it] = sum((1<<(m-1-i))*(x==y) for i,x,y in zip(range(m), word, target))
                        
        for candidate in range(1<<m):
            if any(candidate | masks[j] == masks[j] for j in range(n)): continue

            stack = []
            for it in range(m-1, -1, -1):
                if candidate & (1<<it):
                    stack.append(target[-it-1])
                else:
                    if stack and stack[-1].isdigit():
                        stack[-1] = str(int(stack[-1])+1)
                    else:
                        stack.append("1")

            cand = "".join(stack)
            best = min(best, "".join(stack), key=len)
            if len(best) == len(str(m)): break

        return best