139. Word Break

https://leetcode.com/problems/word-break/

Python

Trie with BFS

class Solution:
    EOS = '$'
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        trie = {}
        for word in wordDict:
            cur = trie
            for letter in word:
                cur = cur.setdefault(letter, {})
            cur[self.EOS] = True

        queue = [trie]

        for letter in s:
            new_queue = []
            is_seen = False
            while queue:
                node = queue.pop()
                if letter not in node:
                    continue

                node = node[letter]
                new_queue.append(node)

                if self.EOS in node and not is_seen:
                    new_queue.append(trie)
                    is_seen = True
            queue = new_queue

        return trie in queue

Javascript

var wordBreak = function(s, wordDict) {
   const recursive = function(start, memo = {}) {
    if (start === s.length) return true;
    if (memo[start] !== undefined) return memo[start];

    for (let i = start + 1; i <= s.length; i++) {
      const partial = s.substring(start, i)
      for (const word of wordDict) {
        if (partial === word && recursive(i, memo)) {
          return memo[start] = true;
        }
      }
    }
    return memo[start] = false;
  }

  return recursive(0)
};