Cracking the Word Break Problem.

First let's understand why this problem is important to understand?

and that we know the technique to solve it.

Scenario:

You're a codebreaker for the Allied forces during World War II. The enemy is sending encrypted messages without spaces between words. Your team has intercepted a list of common words the enemy uses in their communications. Your mission is to determine if an intercepted message can be deciphered using the known word list.

Problem: Given an intercepted message (a string without spaces) and a list of known enemy words, determine if the message can be completely broken down into words from the list.

Success case: 

transmission ="attackatdawn"
codebook =["attack","at","dawn","day","night"]

Failure case: 

transmission = "retreatatnoon" 
codebook = ["attack", "at", "dawn", "day", "night"]

Some other application of word break problems are:

1. Natural Language Processing (NLP):
2. It's fundamental in text segmentation, particularly for languages without clear word boundaries (like Chinese).
3. Search Engines:
4. Improves query understanding and processing, especially for long or compound queries.
5. Algorithmic Techniques:
6. Demonstrates the power of dynamic programming in solving complex problems efficiently.

Now, that we know why this is important?

let's see how we can solve it?

we are give

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

from the examples we can conclude :

1. We need to iterate over the string 's'
2. we also need to iterate over wordDict array, which has list of possible words
3. next we somehow need to check a substring from s, is in wordDict?
4. if it is, we also need to make sure, prevCheck was true meaning prevWordCheck was also in the array wordDict.

pseduocode

var wordBreak = function(s, wordDict) {
 for(i iterate over s){
     for(let word of wordDict){
      // check if the word.length < i so that still are valid 
      // const newWords = s.substring( using i & word.length)
      // prevWord =s.substring(from prev cycle) was in wordDict 

      // also make sure prevWord was a word in the wordDict        
      if(newWord === word & prevWord){
        store result = true
       }
      }  
     }
    }

here while computing:

1. we need to make sure we are in the bound, while manipulating or checking the words in array or in string s.
2. we need an array we will call dp i.e dynamic programming to store the result
3. at the end we will return the result

function finalRevision(s, wordDict){
    // to store the result
    const dp = new Array(s.length + 1).fill(false)
   // intializing the 1st element to true to build the result
    dp[0] = true

    for(let i = 0; i <= s.length; i++){
        for(word of wordDict){
            if(word.length <= i){
                // form a word
                const start = i - word.length
                const newword = s.substring(start, i)
                // if prevWord was valid && new word is valid
                if(dp[start] && newword === word){
                    dp[i] = true
                }
            }
        }
    }

  /*
  this last index will be true if prev was true
   prev will be true if prev of prev was true
  prev of Prev will be true if prev of prev of prev was true

  thus sending the last index of array.
  */
    return dp[s.length]
}

key note: in pretty much all of the comparison we have <=