Fueled on Bacon

Tag: Medium problems

JS LeetCode Solutions – Word Break II

So today I’m solving the Word Break II, original problem statement here.

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
  const arr = s.split("")  
  const n = arr.length
  const result = new Array(n + 1).fill(0)
  result[0] = 1
  for(let i = 0; i < n; i++){
      if(result[i] == 0)
          continue
      for(const w of wordDict){
          for(let j = 0; j < w.length; j++){
              if(arr[i+j] !== w[j])
                  break
              if(j == w.length - 1){
                  result[i + j + 1] = 1
              }
          }
      }
  }
  return result[n] == 1
};

Quick recap the goal is to see if the input string can be produced exactly from any combination of words (duplicates allowed) of the array of words being passed in as the second argument.

Now, I took a look at this problem last night and I tried to quickly solve it with some combination of a Trie and some clever loops. The result was “almost” solving the problem, passing 30 out of 50 tests, and confusing myself.

This morning I solved it by letting it be a typical dynamic programming problem, and keeping the logic clear with some for loops.

Okay, so this is a simple 1-dimensional dynamic programming problem. What does that mean?

It means that there’s a way to find a “subproblem”, use a table to keep track of intermediate results, and use some exit condition to determine the output of the function.

The subproblem

At the core of this problem is naive string matching. We pick a starting point, we pick a word, and go letter by letter looking for a match.

The trick is, what do we do when we find a match?

And the intuition is, we keep track of where matches happened in a result array.

In the setup, you can see that I made a result array 1 element longer than the input string, and populated it with 0’s.

Whenever I find a match, I set the element at “i + j + 1” to 1. Why?

Well, in the context of this function, i represents the index where we’re starting our word match from, j represents the length of the current word, and we add 1 to indicate the next index where we should begin string matching.

Only beginning the matching process from certain indices really cuts down on the amount of brute force matching we have to do.

At the end of this algorithm, we’re going to have a result array with 1’s indicating every point at which there was a successful group of 1 or more combinations of word matches.

If the last element of the result array gets set to 1, that is a necessary and sufficient condition to determine that there is at least 1 way to use a combination of words in the dictionary array to compose the input string.

Related Articles:

FILTER ARTICLES

DATE
TAGS
MORE FROM FOB

Let's get started

Just let us know the basics and we'll send you a Slack invite to discuss with the whole team.

What are we going to be talking about?