0

Word break problem dynamic programming

Problem :

Given a string and an array of words, find out if the input string can be bro­ken into a space-separated sequence of one or more words.

For example,

inputDict = ["I" , "have", "ha", "dog"]

inputStr = "Ihavedog"
Output: "I ha have dog"

inputStr ="thisisadog"
Output: String can not broken.

Logic for Recursive Solution :

• Traverse the given input string.
• Take a blank string and keep adding one char­ac­ter at a time to it (or prefix).
• If prefix exist in the dic­tio­nary then add it to the answer and make recur­sive call to the rest of the string (or suffix).
• If any of the recur­sive calls returns false then back­track and remove the prefix from the answer string. And again keep adding the char­ac­ters to string to create new prefix.
• If all the recur­sive calls return true it means string has been bro­ken successfully.

Solution :

Using For loop

Using While loop

---

---

---