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

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

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