LeetCode Entry
139. Word Break
If a word is a wordDict concatenation
139. Word Break medium
blog post
substack
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)
}