Word break problem dynamic programming
Given a string and an array of words, find out if the input string can be broken into a space-separated sequence of one or more words.
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 character at a time to it (or prefix).
- If prefix exist in the dictionary then add it to the answer and make recursive call to the rest of the string (or suffix).
- If any of the recursive calls returns false then backtrack and remove the prefix from the answer string. And again keep adding the characters to string to create new prefix.
- If all the recursive calls return true it means string has been broken successfully.
Using For loop
Using While loop