Word Game: Find All Valid Words Formable from a Set of Letter Tiles. LeakCode

Question Details

Problem

You have a collection of letter tiles (possibly with duplicates) and a dictionary of valid words. Find all unique valid words that can be formed using any subset of the tiles (each tile used at most once).

python
def find_valid_words(tiles: list[str], dictionary: set[str]) -> list[str]:
    # tiles: list of single uppercase letters, e.g. ["A","A","B","T"]

**Returns** sorted list of unique valid words
    pass

Example:

tiles = ["A", "A", "B", "T"]
dictionary = {"BAT", "TAB", "AAB", "AT", "BAA", "AABB"}
-> ["AT", "BAT", "TAB"]
# "AAB" not valid (only 1 B available but 2 A's -- wait: 2 A's ARE available,
#  so "AAB" is valid if in dictionary)

Round 1 Coding

Implement the search using backtracking with a frequency map of available tiles.

Follow-ups

How do you use a trie (prefix tree) to prune the search space early when no word in the dictionary starts with the current prefix?
What is the worst-case time complexity with and without trie pruning?
How would you handle blank tiles (wildcards) that can represent any letter?
If the dictionary contains 500,000 words, what is a practical strategy to avoid memory issues with the trie?

Full Details

Problem

You have a collection of letter tiles (possibly with duplicates) and a dictionary of valid words. Find all unique valid words that can be formed using any subset of the tiles (each tile used at most once).

python
def find_valid_words(tiles: list[str], dictionary: set[str]) -> list[str]:
    # tiles: list of single uppercase letters, e.g. ["A","A","B","T"]

**Returns** sorted list of unique valid words
    pass

Example:

tiles = ["A", "A", "B", "T"]
dictionary = {"BAT", "TAB", "AAB", "AT", "BAA", "AABB"}
-> ["AT", "BAT", "TAB"]
# "AAB" not valid (only 1 B available but 2 A's -- wait: 2 A's ARE available,
#  so "AAB" is valid if in dictionary)

Round 1 Coding

Implement the search using backtracking with a frequency map of available tiles.

Follow-ups

How do you use a trie (prefix tree) to prune the search space early when no word in the dictionary starts with the current prefix?
What is the worst-case time complexity with and without trie pruning?
How would you handle blank tiles (wildcards) that can represent any letter?
If the dictionary contains 500,000 words, what is a practical strategy to avoid memory issues with the trie?

Free preview. Unlock all questions →

Topics

Coding Onsite Phone

More from Dropbox

Reddit Dropbox Software Interview Coming Up – Recruiter Mentioned Concurrency/Multithreading Will Be Part of the Coding Round – Any Experience? 1p3a Dropbox Infra Software Engineer Metadata Online Assessment Experience LeetCode Dropbox Onsite LeetCode PocketPills | SDE2 | GGN | Dec 24 LeetCode Avalara | SDE1 | Pune | Oct 2022 [Reject] (Ghosted)