Word Break II

Lessons learned: DFS

Feb 04, 2021

👋 Hello! I’m gathering feedback on SWE Prep. If you like to provide suggestions or feedback, let us know on this survey here!

Question: Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

For example,

Input:"swelolprep"
Dictionary: ["swe", "swel", "ol", "lol", "prep"],
Expected outcome: ["swel ol prep", "swe lol prep"].

Solution

This problem is very similar to Word Break post last week. However, instead of using a boolean array to track the match positions, we need to return the actual words.

Approach 1: Depth First Search

We can use depth first search to get all the possible paths, i.e., the list of strings. The following diagram shows the structure of the tracking array.

See Approach 1

We’re done!

Interested in breaking into Computer Science? Eager to expand your knowledge base and learn new things? Enjoy problem solving? If so, this newsletter is for you. Subscribe to get fully explained interview prompts commonly given in engineering interviews, from Arrays to Dynamic Programming. Questions come out weekly and are also categorized by subject and difficulty.

Subscribe to get full access to the newsletter. Never miss an update.