Greedy Tokenization With Dictionary | Dataford Interview Questions

Perform longest match greedy tokenization on a given text using a dictionary.

Implement tokenize(text, dictionary). At each text position, select the longest dictionary word that matches the remaining text, append it to the result, and advance by its length. If no dictionary word matches, emit the current character as a one-character token and advance by one. Matching is case-sensitive, and dictionary words are non-empty.

Input: a string text and a list of dictionary strings. Output: a list of tokens whose concatenation equals text.

Example: text = "googlecloud", dictionary = ["go", "google", "cloud"] returns ["google", "cloud"] because "google" is the longest match at index 0.

Constraints: 0 <= len(text) <= 9999, 0 <= len(dictionary) <= 10^4, and each dictionary word has length at most 100.

Constraints

0 <= len(text) <= 9999
0 <= len(dictionary) <= 10000
1 <= len(word) <= 100 for every dictionary word
Matching is case-sensitive
Dictionary words may be duplicated

Function Signature

def tokenize(text, dictionary):

Your question is Greedy Tokenization With Dictionary. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem