Word Break II

HardPython00:00

Practice interviewer

In session

5 left

00:00

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

You need to log in / sign up to run or submit.

Problem

Given a string and a dictionary of words, return all possible sentences where the string can be segmented into a space-separated sequence of one or more dictionary words (Word Break II).

Asked in the Onsite Round 2 stage. Coding round where candidate was asked to write code, dry run it, and explain runtime complexity.

Input and Output

Implement def word_break(s, wordDict):. s is a string and wordDict is a list of unique non-empty strings. Return a list of sentences, or an empty list when no segmentation exists. Each sentence must use the entire string, and words must be separated by single spaces. The output order does not matter.

Constraints

0 <= len(s) <= 20
1 <= len(wordDict) <= 1,000
Each dictionary word is non-empty and has length at most 20
The dictionary contains unique lowercase words
Return every valid sentence, and return an empty list when none exists

Function Signature

def word_break(s, wordDict):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output