竟然超时了我去。。。
这题的正确姿势是sliding window.
这里还是基本遵循了String题型 的处理方式, 双指针。
有一个比较厉害的就是它初始化了一个int[] arr 来存放字母出现次数。这样的话我们就不需要nlogn来排序了。
只要字母出现次数和target string 一样。 count 变量有点厉害。左指针指向头,右指针往后走。如果matching,说明左指针那里是start point, 加入list。
sliding window的地方在最后一行。我们一直maintain 一个window of size P.length. 如果超了,我们马上把左指针往右边移动。hash[s.charAt[left++]]++>=0 这个非常tricky。 意思就是如果我们本身左指针指着的start的char 是在hash count里的。那么当移除这个char的时候,表示我们距离matching p需要多一个字,所以count++。
hash值的--和++是最难理解的。主要由于他这个代码太concice了,其实意思就是如果target的某字符字数还没被完全抵消掉,我们count--。 如果这个字符抵消成0了,再遇到这个字符我们不会去decrease count。
++是因为如果我们把left 移动,kick out first char. 我们需要increase char 次数。
他最厉害的就是当它发现ok,我这一段anagram是符合的时候,移动left pointer的时候,它顺带把left pointer correspond的那个letter count 升回来了!这个思维太可怕了
My solution:
上面那个solution我是真的想不出来。主要卡在如果我decrement 了word letter count的话,下一个String anagram 我还怎么判断。我这个暴力做法是不断renew一个新的word count array. 非常慢。。。