Search⌘ K
AI Features
Home
Courses
Grokking Dynamic Programming Interview in JavaScript

Word Break II

Understand how to break a string into valid dictionary words and return all possible sentences. Explore both naive recursive and optimized dynamic programming approaches including top-down memoization and bottom-up tabulation to improve efficiency.

We'll cover the following...

Statement

Given a string s and a dictionary of strings wordDict, add spaces to s to break it up into a sequence of valid words from wordDict. We are required to return all possible sequences of words (sentences). The order in which the sentences are listed is not significant.

Note: The same dictionary word may be reused multiple times in the segmentation.

Let’s say we have a string s = “catsanddog” and the word dictionary wordDict = [“cat”, “and”, “cats”, “dog”]. Of all the possible sentences that may be formed, consider the sentence “cats and dog”. These are the words in our sentence:

  • “cats”
  • “and”
  • “dog”

and they are all present in the given dictionary.

We can break up s to form a different sentence, e.g., “cat sand dog”, but “sand” is not a word in our dictionary so we cannot consider this sentence as a valid sentence.

Constraints:

  • 1≤1 \leq s.length ≤60\leq 60

  • 1≤1 \leq wordDict.length ≤1000\leq 1000

  • 1≤1 \leq wordDict[i].length ≤60\leq 60

  • s as well as all the strings in wordDict consist only of lowercase English letters.

  • All the strings in wordDict are unique.

Examples

No.

s

wordDict

Output

1

"catsanddog"

["cat", "and", "cats" , "sand", "dog"]

["cats and dog", "cat sand dog"]

2

"catsandog"

["cat", "and", "cats" , "sand", "dog"]

[ ]


3


"pineapplepenapple"


["apple", "pen", "applepen", "pine", "pineapple"]

["pine apple pen apple",

"pineapple pen apple",

"pine applepen apple"]

Try it yourself

Implement your solution in the following playground:

JavaScript
usercode > main.js
function wordBreak(s, wordDict) {

    // Your code will replace this placeholder return statement.

    return []

}



export { wordBreak };
Word Break II

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach

The naive approach to solve this problem is to use a traditional recursive strategy in which we take each prefix of the query string s, and compare it to each word in the dictionary. If it matches, we take the string’s suffix and repeat the process. ...

Ask