Given a string, s, and a dictionary of strings, wordDict, check if s can be segmented into a space-separated sequence of one or more dictionary words. If yes, return TRUE; else, return FALSE.

word-break.js

function wordBreak(s, wordDict) {
  // we initialize the dp array of length s.length + 1
  // dp[i] answers the question, whether or not the string up to but not including s[i] can be broken up to words
  // so dp[s.length] will answer the initial question of whether or not the whole string can be broken up to words
  const dp = Array(s.length + 1).fill(false);
  // dp[0] is true because string up to but not inclusing s[0] is an empty string so we consider it a valid word
  dp[0] = true;
  // start iteration from the second character
  for (let i = 1; i <= s.length; ++i) {
    // inner loop starts from the first character, up to i
    for (let j = 0; j < i; ++j) {
      // consider substring from j to i
      const slice = s.slice(j, i);
      // if this substring is in the dictionary,
      // we need to check whether or not the string that comes before this substring can be broken up to words
      if (wordDict.find((word) => word === slice) && dp[j]) {
        // we found case when string up to but not including s[i] can be broken into words
        // so record the subproblem solution
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

export { wordBreak };

// tc: O(n^2)
// sc: O(n)