3291. Minimum Number of Valid Strings to Form Target I
Array String Binary Search Dynamic Programming Trie Segment Tree Rolling Hash String Matching Hash Function
Read the full problem statement on LeetCode.
Difficulty: medium Acceptance: 20% Topics: Array, String, Binary Search, Dynamic Programming, Trie, Segment Tree, Rolling Hash, String Matching, Hash Function
View full problem on LeetCode Reading material
Reference solution (spoiler · python)
# Time: O(n + w * l)
# Space: O(n + w * l)
# rolling hash, hash table, two pointers, sliding window, dp
class Solution(object):
def minValidStrings(self, words, target):
"""
:type words: List[str]
:type target: str
:rtype: int
"""
MOD, P = 10**9+7, 131
power = [1]
for _ in xrange(len(target)):
power.append(power[-1]*P%MOD)
lookup = set()
for w in words:
h = 0
for x in w:
h = (h*P+(ord(x)-ord('a')+1))%MOD
lookup.add(h)
dp = [0]*(len(target)+1)
left = h = 0
for right in xrange(len(target)):
h = (h*P+(ord(target[right])-ord('a')+1))%MOD
while right-left+1 >= 1 and h not in lookup:
h = (h-(ord(target[left])-ord('a')+1)*power[(right-left+1)-1])%MOD
left += 1
if right-left+1 == 0:
return -1
dp[right+1] = dp[(right-(right-left+1))+1]+1
return dp[-1]
# Time: O(n + w * l)
# Space: O(n + t), t is the total size of ac automata trie
import collections
class AhoNode(object):
def __init__(self):
self.children = collections.defaultdict(AhoNode)
# self.indices = []
self.suffix = None
# self.output = None
self.length = 0 # added
class AhoTrie(object):
def step(self, letter):
while self.__node and letter not in self.__node.children:
self.__node = self.__node.suffix
self.__node = self.__node.children[letter] if self.__node else self.__root
return self.__get_ac_node_outputs(self.__node)
def __init__(self, patterns):
self.__root = self.__create_ac_trie(patterns)
self.__node = self.__create_ac_suffix_and_output_links(self.__root)
def __create_ac_trie(self, patterns): # Time: O(n), Space: O(t)
root = AhoNode()
for i, pattern in enumerate(patterns):
node = root
for l, c in enumerate(pattern, 1): # modified
node = node.children[c]
node.length = l # added
# node.indices.append(i)
return root
def __create_ac_suffix_and_output_links(self, root): # Time: O(n), Space: O(t)
queue = collections.deque()
for node in root.children.itervalues():
queue.append(node)
node.suffix = root
while queue:
node = queue.popleft()
for c, child in node.children.iteritems():
queue.append(child)
suffix = node.suffix
while suffix and c not in suffix.children:
suffix = suffix.suffix
child.suffix = suffix.children[c] if suffix else root
# child.output = child.suffix if child.suffix.indices else child.suffix.output
return root
def __get_ac_node_outputs(self, node): # Time: O(z)
return node.length # modified
# result = []
# for i in node.indices:
# result.append(i)
# output = node.output
# while output:
# for i in output.indices:
# result.append(i)
# output = output.output
# return result
# ac automata trie
class Solution2(object):
def minValidStrings(self, words, target):
"""
:type words: List[str]
:type target: str
:rtype: int
"""
trie = AhoTrie(words)
dp = [0]*(len(target)+1)
for i in xrange(len(target)):
l = trie.step(target[i])
if not l:
return -1
dp[i+1] = dp[(i-l)+1]+1
return dp[-1]
# Time: O(w * (l + n))
# Space: O(l + n)
# kmp, dp
class Solution3(object):
def minValidStrings(self, words, target):
"""
:type words: List[str]
:type target: str
:rtype: int
"""
def getPrefix(pattern):
prefix = [-1]*len(pattern)
j = -1
for i in xrange(1, len(pattern)):
while j+1 > 0 and pattern[j+1] != pattern[i]:
j = prefix[j]
if pattern[j+1] == pattern[i]:
j += 1
prefix[i] = j
return prefix
def KMP(text, pattern, callback):
prefix = getPrefix(pattern)
j = -1
for i in xrange(len(text)):
while j+1 > 0 and pattern[j+1] != text[i]:
j = prefix[j]
if pattern[j+1] == text[i]:
j += 1
callback(i, j)
if j+1 == len(pattern):
j = prefix[j]
def update(i, j):
lookup[i] = max(lookup[i], j+1)
lookup = [0]*len(target)
for w in words:
KMP(target, w, update)
dp = [0]*(len(target)+1)
for i in xrange(len(target)):
if not lookup[i]:
return -1
dp[i+1] = dp[(i-lookup[i])+1]+1
return dp[-1]
# Time: O(w * l + n * l)
# Space: O(n + t), t is the total size of trie
# trie, dp
class Solution4(object):
def minValidStrings(self, words, target):
"""
:type words: List[str]
:type target: str
:rtype: int
"""
class Trie(object):
def __init__(self):
self.__nodes = []
self.__new_node()
def __new_node(self):
self.__nodes.append([-1]*26)
return len(self.__nodes)-1
def add(self, w):
curr = 0
for c in w:
x = ord(c)-ord('a')
if self.__nodes[curr][x] == -1:
self.__nodes[curr][x] = self.__new_node()
curr = self.__nodes[curr][x]
def query(self, target, i):
curr = 0
for l in xrange(len(target)-i):
x = ord(target[i+l])-ord('a')
if self.__nodes[curr][x] == -1:
return l
curr = self.__nodes[curr][x]
return len(target)-i
trie = Trie()
for w in words:
trie.add(w)
lookup = [0]*len(target)
for i in xrange(len(target)):
l = trie.query(target, i)
for nl in xrange(1, l+1):
lookup[i+nl-1] = max(lookup[i+nl-1], nl)
dp = [0]*(len(target)+1)
for i in xrange(len(target)):
if not lookup[i]:
return -1
dp[i+1] = dp[(i-lookup[i])+1]+1
return dp[-1]
Solution from kamyu104/LeetCode-Solutions · MIT