FastPrepWord Break II

Word Break II

Google logoGoogle● HardNEW GRADONSITE INTERVIEW
Learn

Problem statement

Given a lowercase string s and a dictionary of distinct lowercase words, return every sentence formed by inserting spaces into s so that every segment is a dictionary word.

Every character of s must be used exactly once and in order. Return sentences in ascending lexicographic order. Return an empty array when no sentence is possible.

Function

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

Examples

Example 1

s = "catsanddog"dictionary = ["cat","cats","and","sand","dog"]return = ["cat sand dog","cats and dog"]

Both segmentations use only dictionary words; lexicographic order places cat sand dog first.

Example 2

s = "pineapplepenapple"dictionary = ["apple","pen","applepen","pine","pineapple"]return = ["pine apple pen apple","pine applepen apple","pineapple pen apple"]

There are three complete segmentations.

Example 3

s = "catsandog"dictionary = ["cats","dog","sand","and","cat"]return = []

No dictionary segmentation consumes the complete string.

Constraints

  • 1 <= s.length <= 20.
  • 1 <= dictionary.length <= 1000.
  • All strings contain lowercase English letters, dictionary words are distinct, and every word is nonempty.

More Google problems

See Google hiring insights
public String[] wordBreakSentences(String s, String[] dictionary) {
    // Write your code here.
}
s"catsanddog"
dictionary["cat","cats","and","sand","dog"]
expected["cat sand dog", "cats and dog"]
Checking account…