code.ashish.me

Atom feed

Recently added: 02 Count Of Subset Sum, 416 Partition Equal Subset Sum, 01 Subset Sum, 518 Coin Change 2, 983 Minimum Cost For Tickets

139 Word Break

/**
 *
 * Ashish Patel
 * e: ashishsushilPatel@gmail.com
 * w: https://ashish.me
 *
 */

const wordBreak = (s, wordDict) => {
  let cache = new Array(s.length).fill(false)
  cache[s.length] = true
  for (let i = s.length - 1; i >= 0; i--) {
    for (let j = 0; j < wordDict.length; j++) {
      if (i + wordDict[j].length <= s.length && s.slice(i, wordDict[j].length + i) == wordDict[j]) {
        console.log(s.slice(i, wordDict[j].length))
        cache[i] = cache[i + wordDict[j].length]
        if (cache[i]) {
          break
        }
      }
    }
  }
  return cache[0]
}

console.log(wordBreak('leetcode', ['leet', 'code']))

Created 2022-03-22T00:02:46+00:00 · Edit