推特 电面

sfsttz 发表于 2017-5-9 13:13
楼主的意思是统计s2 的frequency 然后s1里用双指针找正好覆盖frequency的子串吗？这样是O(n)呀

因为不满足条件的话还要copy一下原来的map，所以是O(n^2)

weitongg 发表于 2017-5-9 14:00
楼主是投的社招吗？

我投的new grad

mmmfighting 发表于 2017-5-10 11:53
上上周约的

这题是利口无硫其

跟76题类似 建议看一那里的discussion 有一个O(n) solution的模版很有帮助

mmmfighting 发表于 2017-5-10 11:55
因为不满足条件的话还要copy一下原来的map，所以是O(n^2)

用slide window，如果不匹配不需要完整恢复整个map，只需要把s1开始匹配的第一个再恢复到map里面去就好了，所以时间复杂度还是O(n)