FastPrep
Problem · String

Word Break II

Learn this problem
● HardInMobi logoInMobiFULLTIMEPHONE SCREEN

Problem statement

Given a non-empty lowercase string s and an array wordDict of distinct lowercase words, insert spaces into s to form valid sentences.

Each segment of a sentence must appear in wordDict. A dictionary word may be used more than once, and every character of s must belong to exactly one segment.

Return every distinct valid sentence in lexicographically increasing order. If no valid sentence can be formed, return an empty list.

Function

wordBreak(s: String, wordDict: String[]) → List<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. Both sentences use only dictionary words and appear in lexicographic order.

Example 2

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

There are three complete segmentations. The word apple is reused where needed, and the resulting sentences are returned in lexicographic order.

Example 3

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

No sequence of dictionary words covers every character of s, so the result is empty.

Constraints

  • 1 <= s.length <= 20
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 10
  • s and every word in wordDict contain only lowercase English letters.
  • All words in wordDict are distinct.

More InMobi problems

drafts saved locally
public List<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