FastPrepWord Break II
Problem · String

Word Break II

Learn this problem
● HardWex logoWexFULLTIMEPHONE 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. Sentences must be sorted 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. The judged order is lexicographic.

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 <= 16.
  • 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.

More Wex 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