# 04.08.2023 [139. Word Break]

If a `word` is a `wordDict` concatenation

04.08.2023

139. Word Break medium
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/298

Problem TLDR

If a word is a wordDict concatenation

Intuition

To quickly find out if a sequence, we can use Trie. Then, we can search with DFS any possible split. As the result only depends on the argument, we can safely cache it.

Approach

Write a Trie and DFS, no tricks here.

Complexity

• Time complexity:
  O(wn), w—is words count in s

• Space complexity:
  O(w + 26^l), l—is the longest word in a dict

Code

    class Trie(var isWord: Boolean = false) { val next = mutableMapOf<Char, Trie>() }
    fun wordBreak(s: String, wordDict: List<String>): Boolean {
        val root = Trie()
        wordDict.forEach { 
          var t = root
          it.forEach { t = t.next.getOrPut(it) { Trie() } }
          t.isWord = true
        }
        val cache = mutableMapOf<Int, Boolean>()
        fun dfs(pos: Int): Boolean = pos == s.length || cache.getOrPut(pos) {
          var t: Trie? = root
          s.withIndex().asSequence().drop(pos).takeWhile { t != null }
          .any { (i, c) ->
            t = t?.next?.get(c)
            t?.isWord == true && dfs(i + 1)
          }
        }
        return dfs(0)
    }