求问amazon p matching score思路

原帖在 https://www.1point3acres.com/bbs/thread-918662-1-1.html 第二题
除了暴力解对于每一个start index模拟一遍还有别的做法吗，回复必加米zszszs

做k次slicing window就行了
要理解为什么能用slicing window， 你得先发现遍历原字符串是存在字符串复用的可能性的。
传统的sliding window每次往右边移动一格就能得到一个需要evaluate的substring，但这个题因为有个长度为k的间隔 你每次要往右移动k个坐标，才能得到下一个要evaluate的substring 然后你会发现这个substring跟你刚才evaluate的那个只有首尾两个字符之差。比如原字符串string1是abcdefgh ，string2是ace，k = 2，那就相当于对aceg做一次定长为3的sliding window 对bdfh也做一次，总共分成了k个需要进行sliding window的substring

差不多就是楼上的思路 如果不理解的话可以去做下30 差不多就是那个的青春版

你的帖子里已经讨论了sliding window做法了。的确可以优化。另外一点：sliding window 对应的HashMap是否与S2匹配的判断，讨论中并没提到，不需要遍历判断匹配，可以O1来做

adslusb 发表于 2022-8-18 15:49
你的帖子里已经讨论了sliding window做法了。的确可以优化。另外一点：sliding window 对应的HashMap是否与 ...

想问下这里的遍历判断怎么O1啊，26个字母

DiegoCao 发表于 2022-08-18 19:06:20
想问下这里的遍历判断怎么O1啊，26个字母

把s2用HashMap总结出来，用sliding window里的字母来做减法，注意这里允许出现负数。如果频率=0则把这个entry从map里删掉。反之加入map。当map size为0时则完全匹配。map的物理意义是：还差多少字母以及各多少个才能完全匹配。

adslusb 发表于 2022-8-18 23:26
把s2用HashMap总结出来，用sliding window里的字母来做减法，注意这里允许出现负数。如果频率=0则把这个en ...

明白了～感谢