Dynamic Programming 1D Flashcards
- 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/
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]
- 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/
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
- 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/
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)
