How should I practice Word Break II: All Sentences?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft phone screen problems in FastPrep.

Is Word Break II: All Sentences associated with Microsoft?

FastPrep tags this as a Microsoft phone screen coding practice problem when the problem catalog has that company and stage context.

Word Break II: All Sentences

Microsoft● HardFULLTIMEPHONE SCREEN

Learn

Problem statement

Given a nonempty string s and an array of distinct words wordDict, return every way to split the entire string into dictionary words.

Represent each split as a sentence with exactly one space between adjacent words. Do not add a leading or trailing space. A dictionary word may be used more than once.

Return the distinct sentences in lexicographically increasing order. If no complete split exists, return an empty array.

Function

wordBreakSentences(s: String, wordDict: String[]) → String[]

Examples

Example 1

s = "redblue"wordDict = ["red","blue","redblue"]return = ["red blue","redblue"]

Either use the two words red and blue, or use the single word redblue. The sentence containing a space sorts first.

Example 2

s = "redgreen"wordDict = ["red","blue"]return = []

The prefix red is valid, but the remaining green cannot be covered by dictionary words.

Example 3

s = "aa"wordDict = ["a","aa"]return = ["a a","aa"]

The word a may be reused, so both a a and aa are valid complete sentences.

Constraints

1 <= s.length <= 20.
1 <= wordDict.length <= 1000.
1 <= wordDict[i].length <= 10.
s and every dictionary word contain only lowercase English letters.
The dictionary words are distinct.
The sum of the lengths of all returned sentences, counting spaces, is at most 10^5.