Algorithmic Problem Solving | Dataford Interview Questions

Your question is Algorithmic Problem Solving. Start with the requirements on the right.

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

Problem

Netskope policy components may arrive as a concatenated string. Given a string s and a dictionary of valid policy tokens, return every possible sentence formed by inserting spaces so that each resulting word appears in the dictionary.

Use memoized depth-first search or an equivalent dynamic programming strategy. Return the sentences in any order. If no complete segmentation exists, return an empty list.

Formal Specification

Implement word_break_sentences(s, wordDict):

s is a non-empty string containing lowercase English letters.
wordDict is a list of unique lowercase strings.
Return a list of strings. Each returned string must contain dictionary words separated by single spaces and must concatenate exactly to s.
A dictionary word may be reused any number of times.

Constraints

1 <= len(s) <= 20
1 <= len(wordDict) <= 1,000
Each dictionary word has length at most 20
The dictionary contains unique lowercase words
The number of valid sentences may be exponential in len(s)

Function Signature

def word_break_sentences(s, wordDict):