Word Break

Lessons Learned: Dynamic Programming

👋 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, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given s ="sweprep", dict = ["swe", "prep"]. Return true because "sweprep" can be segmented as "swe prep".

Solution

Approach 1: Brute Force

This problem can be solved through a brute force check, in which for each string in dict we check if it exists in the string, and return true if we get to the end of the string.

See Approach 1

Approach 2: Dynamic Programming

We can use a dynamic programming approach:

  • Define an array arr[] such that if arr[i] == true, then the substring from 0 to i - 1 can be broken down using the dictionary.

  • Our base case is that arr[0] == true

See Approach 2

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.