Word Break

Try to solve the Word Break problem.

We'll cover the following

Statement#

Given a string, s, and a dictionary of strings, word_dict, check if s can be segmented into a space-separated sequence of one or more dictionary words. If yes, return TRUE; else, return FALSE.

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

Constraints:

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

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

  • 1≤1 \leq word_dict[i].length ≤20\leq 20

  • s and word_dict[i] consist of only lowercase English letters.

  • All the strings of word_dict are unique.

Examples#

Created with Fabric.js 3.6.6 s "catsanddog" TRUE Word Dict "cat" "and" "cats" "sand" "dog" Sample example 1 Inputs Output The possible solution is "cats and dog". -------------------------------------------------------------

1 of 2

Created with Fabric.js 3.6.6 s "catsandog" Word Dict "cat" "and" "cats" "sand" "dog" Sample example 2 Inputs Output FALSE The string can’t be space separated using the given dictionary. -------------------------------------------------------------

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

1

Can the string “pineapplepenapple” be split into sequences separated by spaces using the following words from the dictionary?

[“apple”, “pen”, “applepen”, “pine”, “pineapple”]

A)

Yes

B)

No

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Find all possible prefixes of the input string.

For each prefix, check if it’s contained in the dictionary. If it is, repeat the process with the rest of the string.

For the remaining string, find all possible prefixes in the dictionary. Continue this process until the whole string has been processed.

After processing the whole string, return TRUE if it could be broken into space-separated dictionary words. Otherwise, return FALSE.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
%0 node_01 ag node_11 al node_21 icl node_31 mag node_41 magic node_51 ly node_61 lly
Visualization for Input #2
Word Break

Solution: Unique Paths

Solution: Word Break