LeetCode Entry

140. Word Break II

25.05.2024 hard 2024 kotlin rust

All string splits with dictionary programming

140. Word Break II hard blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/617

Problem TLDR

All string splits with dictionary #hard #dfs #dynamic_programming

Intuition

There are several ways to attack this problem: we can make a Trie or HashSet from the dictionary, then just walk the string for all suffixes and use a Dynamic Programming formula for the answer dp[s] = prefix + dp[s - prefix].

Approach

Let’s try to be clever and reuse the method signature with the cost of performance loss of not using memoization.

Complexity

• Time complexity: \(O(ws^s^2)\), the recursion depth is in the worst case aaaaa is s, at each level we try s times and in each successfull prefix iterating over 2^s next results each prepending s symbols. With memoization it is \(O(w2^s)\). With helper function and the single set precalculation is \(O(w + 2^s)\).

• Space complexity: \(O(ws + 2^s)\), recursion depth is s, each level holds w copy and 2^s result.

Code

    fun wordBreak(s: String, wordDict: List<String>): List<String> = buildList {
        val set = wordDict.toSet()
        for (i in s.indices) if (s.take(i + 1) in set)
            if (i == s.lastIndex) add(s) else
                for (next in wordBreak(s.drop(i + 1), wordDict))
                    add("${ s.take(i + 1) } $next")
    }

    pub fn word_break(s: String, word_dict: Vec<String>) -> Vec<String> {
        let (mut res, set) = (vec![], word_dict.iter().map(|w| w.as_str()).collect::<HashSet<_>>());
        for i in 0..s.len() { let w = &s[0..=i]; if set.contains(w) {
            if i == s.len() - 1 { res.push(w.to_string()) } else {
                for n in Self::word_break(s[i + 1..].to_string(), word_dict.clone()) {
                    res.push(format!("{} {}", w, n).to_string())
                }}
        }}; res
    }