Recursive approach
In this approach, we are using for in loop. The recursive function canWordBreak checks if a given string can be segmented into words from a dictionary. It iteratively slices the input string, checking if the substring exists in the dictionary. If found, it recursively calls itself on the remaining portion of the string. When an empty string is reached, it returns true, indicating success. The function backtracks if no valid segmentation is found and returns false if no valid segmentation exists.
Example: In this example we are using the above-explained approach.
Javascript
function canWordBreak(string, dictionary, result = []) { if (string === "") { return result; } for (let i in string) { const substring = string.slice(0, parseInt(i) + 1); if (dictionary.includes(substring)) { const remainingString = string.slice(parseInt(i) + 1); const wordSegment = canWordBreak(remainingString, dictionary, [...result, substring]); if (wordSegment !== null) { return wordSegment; } } } return null; } let dictionary = ["geeks", "for", "forgeeks"]; let string = "w3wiki"; let result = canWordBreak(string, dictionary); if (result !== null) { console.log(result.join(" ")); } else { console.log("String cannot be broken."); } |
geeks for geeks
JavaScript Program for Word Break Problem
The word break problem is a well-known and fundamental challenge within the field of computer science. The Word Break Problem in JavaScript involves determining if a given string can be segmented into words from a dictionary. It seeks to find a valid combination of dictionary words that compose the entire input string. In this context, a ‘word’ is defined as a consecutive sequence of characters separated by spaces. Meanwhile, the ‘dictionary’ is represented as a collection of valid words.
Table of Content
- Recursive approach
- Dynamic programming
We will explore all the above methods along with their basic implementation with the help of examples.
Contact Us