Word Break | Dataford Interview Questions

Uber Eats may need to validate whether a normalized search string can be assembled from known menu or query tokens. Given a string s and a list wordDict, determine whether s can be segmented into one or more dictionary words. A dictionary word may be used multiple times.

Formal Specification

Implement word_break(s, wordDict).

Input: s, a lowercase string, and wordDict, a list of lowercase strings.
Output: Return True if s can be fully segmented into dictionary words. Otherwise, return False.
Words must cover the entire string, in order, with no unmatched characters.

Constraints

1 <= len(s) <= 300
1 <= len(wordDict) <= 1,000
1 <= len(wordDict[i]) <= 20
s and every dictionary word contain only lowercase English letters
Duplicate dictionary words may appear

Function Signature

def word_break(s, wordDict):

Your question is Word Break. 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