Just given a problem which is basically https://leetcode.com/problems/word-break except you cannot reuse words in the dictionary and the list can contain duplicates. You also must return a list of words that make up the input word. There are multiple possible answers.

Examples

Example 1

"microsoft", ["m", "mi", "c", "o", "o", "ros", "soft", "cro", "r"]
possible answers are(either are accepted):
["mi", "cro", "soft"],
["mi", "c", "r", "o", "soft"]

Example 2

"microsoft", ["m", "mi", "c", "o", "ros", "soft", "r"]
[]
only one 'o' in this case and "cro" is removed, so the word cannot be constructed.

Example 3

"microsoftsoft", ["m", "mi", "c", "o", "o", "ros", "soft", "cro", "r", "s", "o", "fe", "ft"]
["mi", "cro", "soft", "s", "o", "ft"],
["mi", "cro", "s", "o", "ft", "soft"],
["mi", "c", "r", "o", "soft", "s", "o", "ft"],
["mi", "c", "r", "o", "s", "o", "ft", "soft"]

Solution (DFS + Memoization)

I totally fumbled it due to not reading the problem correctly, but came up with this solution afterward:

class Solution:
	memo = {}

	def word_break_memo(self, word, tiles, tiles_set):
		inp = (word, tiles_set)
		if not inp in memo:
			memo[inp] = self.word_breakr(word, tiles, tiles_set)
		return memo[inp]

	def word_breakr(self, word, tiles, tiles_set):
		if not word:
			return []
		else:
			for i in tiles_set:
				tile = tiles[i]
				if word.startswith(tile):
					j = len(tile)
					result = self.word_break_memo(word[j:], tiles, tiles_set - frozenset([i]))
					if result != False:
						return [tile] + result
			return False

	def word_break(self, word, tiles):
		return self.word_break_memo(word, tiles, frozenset(i for i in range(len(tiles))))

Notes on solution

Basically just DFS + Memoization.

The frozenset is a micro-optimization. The alternative was using a list which requires a clone and then a O(N) removal of the element. The frozenset only requires a clone + O(1) removal of an element.

Maybe there's a DP solution I can't think of? I initially tried to use a Trie like in word break, but I don't think(?) it helps here due to not being able to reuse words.

I just want to know if there's a solution with better time complexity.
Found thanks StormRahul!

This solution isn't exactly right because the tiles aren't guaranteed to be in order(maybe other bugs too), but it's close enough for my understanding. Edit: I profiled it and it was about 250x slower than the DFS + Memo lol. So it's almost certainly wrong/unoptimal.

Solution 2 Bitmasking

def  countSetBits(n):
    count = 0
    while (n):
        count += n & 1
        n >>= 1
    return count

def can_spell_b(word, tiles):
    tiles = [t for t in tiles if t in word]

    result = None
    for mask in range(2**len(tiles)):
        new_word = word
        bits = countSetBits(mask)
        for i in range(len(tiles)):
            if mask & (1 << i):
                bits -= 1
                if new_word and tiles[i] in new_word:
                    new_word = new_word.replace(tiles[i], "", 1)
                else:
                    break
        if not new_word and bits == 0:
            result = mask
            break
    if result:
        return [tiles[i] for i in range(len(tiles)) if result & (1 << i)]
    return False