Problem statement

https://binarysearch.com/problems/Blocks-to-Spell-Word/

Solution

We can use bit-dp with states dp(mask, idx), where mask is bitmask of already taken letters in target and idx is the index of current word we traverse.

Complexity

It is O(2^n * m * n) for time and O(2^n * m) for space.

Code

class Solution:
    def solve(self, words, target):
        n, m = len(target), len(words)
        @lru_cache(None)
        def dp(mask, idx):
            if mask == 0: return True
            if idx == m: return False
            if dp(mask, idx + 1): return True
            L = set(words[idx])
            for p in range(n):
                if (mask >> p & 1) and (target[p] in L) and dp(mask ^ (1<<p), idx + 1):
                    return True
            return False

        return dp((1<<n) - 1, 0)