Doordash 23 summer OA

谢谢楼主大神 请问楼主会那道string的题目

匿名用户 发表于 2022-10-04 21:37:33
谢谢楼主大神 请问楼主会那道string的题目

这个题有数据范围吗，我能想到一个二分答案加贪心的O(nmlogn)的解法，或许有优化空间，如果时间复杂度太高我就再想想

补充内容 (2022-10-05 13:03 +08:00):
想到了O(nlogn)的做法，不急的话明天我开电脑写一下

评论区小伙伴们觉得有用加个米吧，冲刺188好漫长🥹

我要吃熊猫 发表于 2022-10-4 21:58
这个题有数据范围吗，我能想到一个二分答案加贪心的O(nmlogn)的解法，或许有优化空间，如果时间复杂度太高 ...

挺急的哈哈 请问楼主能现在说一下思路么

匿名用户 发表于 2022-10-04 22:07:36
挺急的哈哈 请问楼主能现在说一下思路么

二分答案，假设当前答案为len，那么搞一个长度为len的窗口从左往右去扫第二个字符串，窗口内的字符相当于全部被删除，此时串分为了左半部分和右半部分，那么难点在于如何快速判断左串右串能否分别匹配一串的前缀和后缀，而且匹配到的前后缀需要无重叠。

那么我们需要预处理一个prefixmatch数组，可以用贪心来做，pm(i)表示第二个串前i个字符能作为第一个串的子序列的最小下标。相似的，再预处理出一个suffixmatch数组即可。

补充内容 (2022-10-05 13:18 +08:00):
求米

我要吃熊猫 发表于 2022-10-4 22:16
二分答案，假设当前答案为len，那么搞一个长度为len的窗口从左往右去扫第二个字符串，窗口内的字符相当于 ...

感谢楼主！请问该怎么加米，以及处理字符串后该怎么计算呢

匿名用户 发表于 2022-10-04 22:26:35
感谢楼主！请问该怎么加米，以及处理字符串后该怎么计算呢

假设窗口左右端点是l和r，那么prefixmatch l＜suffixmatch r 即可说明窗口长度是一个可行的答案，那么真实的答案一定比当前答案小，如果窗口扫了一遍都不满足上述条件，说明真实答案一定比当前二分出来的答案大

快速+1就是加米了

我要吃熊猫 发表于 2022-10-4 22:36
假设窗口左右端点是l和r，那么prefixmatch l＜suffixmatch r 即可说明窗口长度是一个可行的答案，那么真实 ...

已加米+1 感谢楼主解答！

这道string题目意思是要让我们求一种删掉string2 character的方法 然后这个方法删掉character后是string1的subsequence然后要让删掉的character（不一定连续）的最右边index剪去最左边index加1最小？
已加米！

霖霖霖 发表于 2022-10-05 00:01:00
这道string题目意思是要让我们求一种删掉string2 character的方法 然后这个方法删掉character后是string1的subsequence然后要让删掉的character（不一

是这个意思 zs