Dynamic programming
In this approach, we are using dynamic programming to check if a string can be segmented into words from a dictionary. It creates an array to store whether substrings are valid and iterates through the string and dictionary. If a valid segmentation is found, it returns true, otherwise false.
Example: Using dynamic programming, the code creates an array arr of size n + 1. It iterates through i and j to check if substrings from j to i exist in the dictionary, setting arr[i] to true if found, allowing it to determine if the input string can be segmented into words.
Javascript
function wordBreak(string, dictionary) { const n = string.length; const arr = new Array(n + 1).fill( false ); arr[0] = true ; for (let i = 1; i <= n; i++) { for (let j in arr) { const subString = string.slice(parseInt(j), i); arr[i] = arr[j] && dictionary.includes( subString) ? true : arr[i]; } } return arr[n]; } const dictionary = [ "Geeks" , "forGeeks" ]; const inputString = "w3wiki" ; const result = wordBreak(inputString, dictionary); console.log(result); |
true
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