FastPrepWord Break II
Problems/Word Break II

Word Break II

Bloomberg LP logoBloomberg LP● HardFULLTIMENEW GRADPHONE SCREENONSITE INTERVIEW
QuestionFunctionExamplesConstraints

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: List<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. 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 LP problems

  • Mutable Stock Price Top KPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
  • Sparse Vector and Matrix OperationsPHONE SCREEN · Seen Oct 2026
  • Add Two Numbers IIPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
All Bloomberg LP interview questionsSee Bloomberg LP hiring insights
Saved
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
      // write your code here
    }

}
Checking account…