Question :
Find the minimum amount of Prefix-Strings
needed to make string B from the given list of strings A.
Input :
4
abc ka efgh k
efghkabc
Output: 3
Constraints:
1 <= N <= 100
1 <= |A| <= 100
1 <= |A[i]| <= 100
1 <= |B| <= 100
My Code
# <-------------------------- IMPORTS -------------------------->
from heapq import heapify, heappush, heappop
from functools import cache
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
# <-------------------------- CODE -------------------------->
class Trie:
def __init__(self):
self.children = defaultdict(lambda: None)
self.isEnd = False
def getASCII(key):
return ord(key) - ord('a')
def solve():
int(input())
words = input().split()
s = input()
n = len(s)
# O(N) Trie insertion
head = Trie()
for word in words:
ptr = head
for ch in word:
idx = getASCII(ch)
if not ptr.children[idx]:
ptr.children[idx] = Trie()
ptr = ptr.children[idx]
ptr.isEnd = True
dp = defaultdict(lambda: defaultdict(lambda: False))
def check(head, i, j):
ptr = head
N = j
I = i
while I < N:
idx = getASCII(s[I])
if not ptr.children[idx]:
break
while ptr.children[idx]:
dp[i][I] = True
I += 1
if I >= N:
dp[i][I] = False
break
ptr = ptr.children[idx]
idx = getASCII(s[I])
# O(N^2) each Trie search call will be O(N) hence O(N^2)
for i in range(n):
check(head, i, n)
# I will now have all substrings that are possible
@cache
def recurr(i, j):
if i >= n or j >= n or i > j:
return 0
final = float('inf')
for k in range(i, j + 1):
if dp[i][k]:
final = min(final, 1 + recurr(k + 1, j))
return final
# O(N ^ 2)
ans = recurr(0, n - 1)
if ans == float('inf'):
print(-1)
else:
print(ans)
# <-------------------------- END -------------------------->
solve()
