Word Break (javascript solution) LeetCode 139.

Word Break (javascript solution) LeetCode 139.

Table of contents

No heading

No headings in the article.

Question link -> https://leetcode.com/problems/word-break/

Question - 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

Solution ->

var wordBreak = function(s, wordDict,list_save={}) {
    if(list_save[s] !==undefined) return list_save[s];
    if(s.length===0) return true;

    for (let word of wordDict){
          const result =  wordBreak(s.slice(word.length),wordDict,list_save)
            list_save[s] = output;
            return true;


    list_save[s] = false;
    return false

Okay, so let me explain the Damn Logic of the above code.

Lets say s="applepenapple" and wordDict=["apple","pen"]

Now, here we have to check if "applepenapple" contains "apple" and "pen" in it.

to do that we are using javascript's string's indexOf method, indexOf returns the index first occurrence of a word passed to this method.

so when in the first iteration when "apple" from the wordDict is passed to the "applepenapple".indexOf("apple"). we will get the result of this === 0 because the word apple is present in "s" and its initial value i.e is at the index 0.

// Also a logic we keep in this question is that we don't check any word in between or // from the last. we always check the initial value

then we again slice the word from the sentence "s" and pass that sliced "s" as the argument for the recursive call to the function "wordBreak" also we are creating and pass a new argument i.e an object which is actually for memoization so that we don't have to recalculate any result again and again.

they are some base cases so

  1. check if the list_save object contains any earlier calculated result if yes then return

  2. check if "s" length is equal to 0 if yes then return true. because slice can only happen if we could find any word inside the sentence "s" and can look at the if condition in the loop for reference.

  3. then in the function, we are saving the result of the recursive call in the "result" variable and we check whether the result is true or false if false we ignore if true then we add that value to the memo object i.e list_save and return true.

  4. In the above step i.e step 3, we see that the "wordBreak" function was returning true or false according to the first two base cases but in those cases, none of them was returning false, So this is our last base case, which means if the length of "s" is not equal to 0 and the list_save object does not contain the result and in the loop if we could not find the word from the dictionaries then something should happen right ? so this is the case to cover that situation we have to return false because we could not find any word from the "wordDict" array in "s" characters.

So, yeah this solves this question.