google新题求解

给定一个 query string 和每个子串以及相应的 weight，需要切分 query string，每个切分如果都在 weight 内，sum 所有的 weight 值，如果某个切分其中一个子串不在 weight 内则返回 -1。求一个 query string 的最大的 weight 值，
例如：query: abcdefg, weights: {“a”: 1, “abc”: 10, “bcd”: 11, “cde”: 30, “e”: 3, “fg”: 5} 应该返回 20。切分是 a、bcd、e、fg。

ypcu327 发表于 2019/12/25 00:37:04
如果内部循环遍历权重的话 感觉时间复杂度是 nmL m是weights这个长度 L是平均每个子串长度 n是query s...

如果将weights做成一个基本的字典树，好像就是nwl（query）+ mwl （建trie）了，w是trie每一层平均的宽度（不大于字母集的大小）

FightForLife 发表于 2019/12/25 00:32:09
dp感觉就是O(n^2)了。遍历index比遍历weight快，因为weight 可能有O(n^2)个值，遍历weigt...

如果内部循环遍历权重的话 感觉时间复杂度是 nmL m是weights这个长度 L是平均每个子串长度 n是query string的长度

ypcu327 发表于 2019-12-25 00:11
dp代表从0到index的位置最大的切分weight是多少 时间复杂度是n2 不知道怎么优化一下

dp感觉就是O(n^2)了。遍历index比遍历weight快，因为weight 可能有O(n^2)个值，遍历weigth就变成O(n^3)了。
dfs也是O(n^2)？因为最多有o(n^2)个子串。

直接dfs或者do?

补充内容 (2019-12-24 07:08):
Dp

onerhao 发表于 2019/12/24 23:07:47
直接dfs或者do?

补充内容 (2019-12-24 07:08):
Dp

怎么dp啊？老哥

dp[index]代表从0到index的位置最大的切分weight是多少 时间复杂度是n2 不知道怎么优化一下

其实题目有点没看懂，什么叫不在weight里？没理解错大意的话不影响大致思路。
dp index如上所述。
对一堆子串做trie，
dp[0]好确定，
大循环i从0到n
循环内从i开始往右j在树上找，更新dpj
n^2，蹲个更优解

或者对子串reverse后做trie，从i开始往左搜树，感觉差不多，看数据了。

为什么不是 a, b, cde, fg 这样值不是更大吗

rocketman2023 发表于 2019-12-25 05:00
为什么不是 a, b, cde, fg 这样值不是更大吗

b没在weights里面，不能被单独切分， 所以结果是-1