1079. Letter Tile Possibilities

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/letter-tile-possibilities
• topics: Backtracking

Description

You have n  tiles, where each tile has one letter tiles[i] printed on it.

Return the number of possible non-empty sequences of letters you can make using the letters printed on those tiles.

Idea

Code

Backtrack

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        seqs = set()
        def backtrack(prev, used_tiles):
            nonlocal seqs
            for i, _ in enumerate(used_tiles):
                if not used_tiles[i]:
                    prev.append(tiles[i])
                    used_tiles[i] = True
                    seqs.add(hash("".join(prev)))
                    backtrack(prev, used_tiles)
                    prev.pop()
                    used_tiles[i] = False
 
        backtrack([], [False] * len(tiles))
        return len(seqs)
 
 
            

Permutations

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        return len(set(hash(t) for n in range(1, len(tiles)+1) for t in permutations(tiles, n)))