Facebook Pixel

Word Break II

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

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

Example 1:

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

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

Example 2:

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

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

Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

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

Output: []

Constraints:

  • 1 <= s.length <= 20
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 10
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.

Solution

We can apply the backtracking1 template to solve this problem. Fill in the logic.

  • is_leaf: start_index == len(s), when all the letters are used.
  • get_edges: w = s[start_index:end_index+1] where start_index <= end_index < len(s), are the possible words starting at start_index.
  • is_valid: is w in wordDict? w is valid if it's in the dictionary.

Implementation

def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
    def dfs(start_index, path):
        if start_index == len(s):
            ans.append(" ".join(path))
            return
        for end_index in range(start_index, len(s)):
            w = s[start_index:end_index+1]
            if w in wordDict:
                path.append(w)
                dfs(end_index+1, path)
                path.pop()
    ans = []
    dfs(0, [])
    return ans

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!


Load More