Given a String array words contains words and an integer array score contains score of each word such that score[i] represents score of word at ith position. Find the max score you can achieve using the combination of words with following rules :
you're given limit integer value, the combination of words used to get maxscore cannot exceed the size limit provided in limit value.
any word can be used multiple times . Eg: words=[sun,moon] score=[5,4] limit=7 then maxscore=10 as the score of combination "sunsun"=5+5=10 and has size 6 which is less than limit 7, hence condition is satisfied.
words are allowed to overlap and form new word. After overlap, the new word can have combined power. Eg. words=[energy, green] score=[4,3] limit=9 then we can use new formed word greenergy with score value =(4+3)=7 here maxscore=7 as greenergy having score=7 and size=9 can be used here
Constraints:
1 <= n <= 100
words array contains unique words
Sample Input
Input: n=3 words=["pack", "acknowledge", "edged"] score=[2,12,3] limit=13 Output: 15 Explaination: Here new combination can be ["pack", "acknowledge", "edged", "acknowledged", "packnowledge", "packnowledged"] with score=[2, 12, 3, 15, 14, 17] So, packnowledged can picked from the combination to form maxscore=17 it also maintain the word limit rule that - size(packnowledged) <= limit 13 <= 13, hence maxscore = 17 as answer.
Does anyone know how to solve this?
I was thinking of DP where the state is the current length and the latest word we've taken ($$$N^2$$$)
Then for the transition we can always try all possible words and see whether it's overlapping or not from the latest word (another $$$N$$$)
To determine the overlapping part, since $$$N$$$ is pretty small, I think we can precompute the overlapping prefix-suffix using a bruteforce method (should be around $$$N^3$$$)
what if there are complete overlaps like ledge knowledgement ? I think prefix and suffix won't work for those scenarios.
What is the constraint on the limit value?
Build a trie containing all words. For each pair $$$(v, c)$$$ where $$$v$$$ is a trie node corresponding to a string $$$s$$$ and $$$c$$$ is a letter, find the longest string $$$t$$$ such that $$$t$$$ is a suffix of $$$sc$$$ and $$$t$$$ exists as a prefix in the trie, let that trie node be $$$w$$$. This can be done in linear time but brute-force is also fine, according to constraints. Now add a labeled edge from $$$v$$$ to $$$w$$$ with a label $$$c$$$ for each $$$(v, c)$$$. You've now built a deterministic finite automaton which recognizes the given set of words. Now, for each trie node $$$v$$$ corresponding to some string $$$s$$$, let the value of the node be the sum of all values of strings that are suffixes of $$$s$$$. Now, the problem is just to find a walk in this graph, starting from the trie root, having the maximum length, that maximizes the sum of values of visited nodes. This can be done by a simple DP.
Why describe Aho-Corasick in full again?
This has runtime of O(limit * sum of string length). It is also easy to do in O((sum of string length)^3 * log limit). Without other constraints given, it is not clear if either of these two what is wanted and/or fast enough.