FastPrep
Problem · Array

Word Break II

Learn this problem
● HardBloomberg logoBloombergFULLTIMEPHONE SCREEN

Problem statement

Given a string s and an array of unique dictionary words wordDict, insert spaces into s so that every resulting token is a dictionary word.

Return every valid sentence in lexicographic order. A dictionary word may be reused any number of times.

Function

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

Examples

Example 1

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

The string can be segmented as cat sand dog or cats and dog. The two sentences are returned in lexicographic order.

Example 2

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

All three sentences concatenate to pineapplepenapple, and dictionary words such as apple may be reused.

Example 3

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

No sequence of dictionary words concatenates to the entire string.

Constraints

  • 1 <= s.length <= 20
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 10
  • s and every wordDict[i] contain only lowercase English letters.
  • All strings in wordDict are unique.
  • The total length of all valid output sentences does not exceed 10^5.

More Bloomberg problems

drafts saved locally
public String[] wordBreak(String s, String[] wordDict) {
  // write your code here
}
s"catsanddog"
wordDict["cat","cats","and","sand","dog"]
expected["cat sand dog", "cats and dog"]
checking account