Dynamic Programming 1D

Question 1

139. Word Break
     Companies: Facebook, Amazon

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = “leetcode”, wordDict = [“leet”,”code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.
Example 2:

Input: s = “applepenapple”, wordDict = [“apple”,”pen”]
Output: true
Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”.
Note that you are allowed to reuse a dictionary word.
Example 3:

Input: s = “catsandog”, wordDict = [“cats”,”dog”,”sand”,”and”,”cat”]
Output: false

Constraints:

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique

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

Answer 1

from collections import defaultdict

class Solution(object):
def wordBreak(self, s, wordDict):
“””
:type s: str
:type wordDict: List[str]
:rtype: bool
“””
Trie = lambda: defaultdict(Trie)
trie = Trie()
for word in wordDict:
cur = trie
for c in word:
cur = cur[c]
cur[”#”] = True
dp = [False] * len(s)
for i in range(len(s)):
cur = trie
if i == 0 or dp[i-1]:
for j in range(i, len(s)):
c = s[j]
if c not in cur:
break
cur = cur[c]
if cur[”#”]:
dp[j] = True
return dp[-1]

less efficient solution

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
words = set(wordDict)
dp = [False] * (n + 1)
dp[0] = True

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break

    return dp[-1]

Question 2

140. Word Break II
     Solved
     Hard
     Topics
     Companies
     Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = “catsanddog”, wordDict = [“cat”,”cats”,”and”,”sand”,”dog”]
Output: [“cats and dog”,”cat sand dog”]
Example 2:

Input: s = “pineapplepenapple”, wordDict = [“apple”,”pen”,”applepen”,”pine”,”pineapple”]
Output: [“pine apple pen apple”,”pineapple pen apple”,”pine applepen apple”]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:

Input: s = “catsandog”, wordDict = [“cats”,”dog”,”sand”,”and”,”cat”]
Output: []

Constraints:

1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.
Input is generated in a way that the length of the answer doesn’t exceed 105.

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

Answer 2

from collections import defaultdict

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        Trie = lambda: defaultdict(Trie)
        trie = Trie()
        for word in wordDict:
            cur = trie
            for c in word:
                cur = cur[c]
            cur["#"] = word
        
        ret = []
        seen = []
        def rec(subs, words):
            if not subs:
                ret.append(" ".join(words))
                return 
            retwords = words
            cur = trie
            for j in range(len(subs)):
                c = subs[j]
                if c not in cur :
                    return
                cur = cur[c]
                if "#" in cur:
                    rec(subs[j+1:], retwords + [cur["#"]])                      
        rec(s, [])
        return ret

Trie + Caching

from functools import cache, reduce
from collections import defaultdict
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        maxLen = reduce(lambda mlen,x: max(len(x), mlen), wordDict, 0)
        wordDict = set(wordDict)
        Trie = lambda: defaultdict(Trie)
        trie = Trie()
        for word in wordDict:
            cur = trie
            for c in word:
                cur = cur[c]
            cur["$"] = word

        @cache
        def rec(i):
            if i == len(s):
                return -1
            
            out = []
            cur = trie
            for j in range(i, len(s)):
                if s[j] not in cur:
                    return out
                cur = cur[s[j]]
                if "$" in cur:
                    res = rec(j+1)
                    if res == -1:
                        out.append(cur['$'])
                    else:
                        for part in res:
                            out.append(" ".join([cur['$'], part]))
            return out
        return rec(0)

O(n2^n) worst case, 2^n worst case

Question 3

472. Concatenated Words
     Hard
     Topics
     Companies
     Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words (not necessarily distinct) in the given array.

Example 1:

Input: words = [“cat”,”cats”,”catsdogcats”,”dog”,”dogcatsdog”,”hippopotamuses”,”rat”,”ratcatdogcat”]
Output: [“catsdogcats”,”dogcatsdog”,”ratcatdogcat”]
Explanation: “catsdogcats” can be concatenated by “cats”, “dog” and “cats”;
“dogcatsdog” can be concatenated by “dog”, “cats” and “dog”;
“ratcatdogcat” can be concatenated by “rat”, “cat”, “dog” and “cat”.
Example 2:

Input: words = [“cat”,”dog”,”catdog”]
Output: [“catdog”]

Constraints:

1 <= words.length <= 104
1 <= words[i].length <= 30
words[i] consists of only lowercase English letters.
All the strings of words are unique.
1 <= sum(words[i].length) <= 105

https://leetcode.com/problems/concatenated-words/description/

Answer 3

Using Trie: Sort the words, add them after checking if they exist in Trie, combination words will have all the words they are comprised of in the Trie by the time we reach to them.
O(2^n)

from collections import defaultdict 
class Solution(object):
    def findAllConcatenatedWordsInADict(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        Trie = lambda: defaultdict(Trie)
        trie = Trie()
        ret = []
        wordsSorted = sorted(words, key=len)
        
        def wordbreak(word, wordTrie):
            dp = [False] * len(word)
            for i in range(len(word)):
                cur = wordTrie
                if i == 0 or dp[i-1]:
                    for j in range(i, len(word)):
                        c = word[j]
                        if c not in cur:
                            break
                        cur = cur[c]
                        if "#" in cur:
                            dp[j] = True
            return dp[-1]

        for word in wordsSorted:
            cur = trie
            if wordbreak(word, trie):
                ret.append(word)
            for c in word:
                cur = cur[c]
            cur["#"] = True
        return ret

Using Cache/Memo ( sort is optimization but not needed)

from functools import cache
class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        
        wordDict = set()
        words = sorted(words, key=len)
        
        @cache
        def rec(i, word):
            if i == len(word):
                return 0
            if word[i:] in wordDict:
                return 1
            sub_words = float('-inf')
            for j in range(i+1, len(word)+1):
                if word[i:j] in wordDict:
                    sub_words = max(sub_words, 1+rec(j, word))
            return sub_words
        output = []
        for word in words:
            sub_words = rec(0, word)
            wordDict.add(word)
            if sub_words > 1:
                output.append(word)
        return output

O(2^n), O(2^n)