FindAllAnagramsInAStringOPT [source code]

public class FindAllAnagramsInAStringOPT {
static
/******************************************************************************/
public class Solution {
    public List<Integer> findAnagrams(String s, String p) { //使用hash table+滑动窗口       
        List<Integer> list = new ArrayList<>();
        char[] chp = p.toCharArray(); 
        char[] chs = s.toCharArray();
        int count = chp.length;
        int left = 0;
        int right = 0;
        int hash[] = new int[256];
        for (char c : chp) {
            hash[c]++;
        }
        while (right < chs.length) {
            char c = chs[right++];
            if (hash[c]-- >= 1) count--;
            while (right - left > chp.length) {
                char prev = chs[left++];
                if (hash[prev]++ >= 0) count++;
            }
            if (count == 0) {
                list.add(left);
            }
        }
        return list;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        FindAllAnagramsInAStringOPT.Solution tester = new FindAllAnagramsInAStringOPT.Solution();
        String[] inputs = {
            "cbaebabacd", "abc",
            "abab", "ab",
            "abdkaabacdkajfl", "babc",
            "abdkaabbacdkajfl", "babc",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            String s = inputs[2 * i];
            String p = inputs[1 + 2 * i];
            System.out.println(s + " VS " + p + " -> " + tester.findAnagrams(s, p));
        }
    }
}

这个是 submission 最优解, 10(99.96);

这个算法的核心思路是sliding window, G4G上面学了一下, 这个算法其实就是我一开始想要做到的avoid backup的算法, 虽然没有 KMP 那么复杂, 但是一定程度上做到了 reuse 历史信息;

这个算法刚开始没有看懂, 是因为这个人的逻辑非常聪明, 把sliding window跟这个问题的逻辑融合的非常紧密, 导致整个代码的逻辑做到了最简化, 看起来有点累人.

看这个核心循环的逻辑:

while (right < chs.length) {  
    char c = chs[right++];  
    if (hash[c]-- >= 1) count--;  
    while (right - left > chp.length) {  
        char prev = chs[left++];  
        if (hash[prev]++ >= 0) count++;  
    }  
    if (count == 0) {  
        list.add(left);  
    }  
}

首先这里他这个逻辑的主要骨干就是, 用一个 counts/hash 的 array 来记录p 里面每个字母的frequency, 然后走 chs, 每当(right) 走到一个字母, 无论这个字母是否在 chp 当中(是 hit 还是 miss), 最后在 hash 里面, 我们都当做是一个hit, 或者当做是一个 downvote;
sliding window算法逻辑上需要处理的一个核心问题就是当 window 移动的时候, 如何更新类似sum 的各种内容. 在算 sum 的题目里面, 这个比较简单, 直接-left + right就行了. 但是这个题目本身没有这么简单.
这里的做法是, 只保留 window 内部的 downvote, 也就是说如果我们 slide window 了, 那么你给 left 的 downvote 要撤销(对应的, 就是还给他一个 upvote), 同时因为 right 即将进入 window, 所以要给他一个 downvote;
如何判断找到了一个 anagram? 他这里的这个 count, 保存的其实是, chp 里面的所有字母里面, 可以继续被 downvote 的余额. 比如 p 是"abc", 那么一开始就是 abc 一人给一个1, 那么 chp 里面所有的字母总共可以被 downvote 3次. babc 的话, 一开始就是4次. 这个数量的初始值刚好等于chp 的长度;

if (hash[c]-- >= 1) count--; 的作用就是 downvote. c 保存的是 right 的 character, 即将进入 window, 所以给一个 downvote;

if (count == 0) {  
    list.add(left);  
}

如果没有余额了, 意思就是当前 window 里面的字母constituency and frequency都跟 chp 一模一样(不然不可能被 downvote 完), 所以可以直接 res.add 了;

while (right - left > chp.length) {  
    char prev = chs[left++];  
    if (hash[prev]++ >= 0) count++;  
}

这个循环完成的就是一个 slide 的过程. 这个 header 判断的虽然是大于, 其实最多只可能超1;
body 里面第一行很简单, 就是移动 left.
hash++这个就是类似一个退款的操作, prev 反正要出去了, 所以要还给他一个 upvote;
count++这个刚开始可能有点无法理解: 要记住我们这里的 count 记录的其实是 chp 的字母的余额. 所以 count 收到退款的前提必须是 prev 是 chp 内部的一个;
可以有两个角度来理解这个 count 的退款:

• 首先记住, 只有处于 window 内部的人才会被 downvote. 如果 prev 不是 chp内部的, 那么 prev 这个时候的 hash 一定是负值(不是 chp 的内部的, hash 初始值是0, 然后加他的时候被 downvote 了, 现在肯定至少是-1), 所以我们踢 prev 的时候, 不需要改变 count. 如果 prev 是 chp 内部的, 那么prev 这个时候的 hash 一定至少是0(我们加进来的时候的 downvote, 每一个 downvote 对应的其实是one occurrence in chp, 所以不论 prev 当时的hash 初始值是多少, 不可能被 downvote 到0以下), 这样的 prev 被踢的时候我们就应该给 count 退款;
• 另外一个角度理解, 其实这里的这一句跟前面的那一句是对应的:

if (hash[c]-- >= 1) count--;  
...  
if (hash[prev]++ >= 0) count++;

加进来的时候, 至少是1, 踢出去的时候, 至少是0, 这个就是 chp 内部的 char 的特征.

这个退款思路也是反映了这个代码的精炼度.
如果看到这里, 基本上这个算法的大体思路已经理解, 剩下的就是一些 var 更新的 Corner Case 的设置和调整了; 注意的是这里虽然说是left and right, 但是(before each iteration)这一个点, window 其实是left .. right - 1的范围. this iteration处理的就是add right, 然后kick left; 这样实际上想要保持的其实是right - 1 - left + 1 == lenP的状态, 所以这里他 slide 的 header 的判断才会使用

这个是 discussion 上面看到的一个类似的版本:

public List<Integer> findAnagrams(String s, String p) {  
    List<Integer> list = new ArrayList<>();  
    if (s == null || s.length() == 0 || p == null || p.length() == 0) return list;  
    int[] hash = new int[256]; //character hash  
    //record each character in p to hash  
    for (char c : p.toCharArray()) {  
        hash[c]++;  
    }  
    //two points, initialize count to p's length  
    int left = 0, right = 0, count = p.length();  
    while (right < s.length()) {  
        //move right everytime, if the character exists in p's hash, decrease the count  
        //current hash value >= 1 means the character is existing in p  
        if (hash[s.charAt(right++)]-- >= 1) count--;   

        //when the count is down to 0, means we found the right anagram  
        //then add window's left to result list  
        if (count == 0) list.add(left);  

        //if we find the window's size equals to p, then we have to move left (narrow the window) to find the new match window  
        //++ to reset the hash because we kicked out the left  
        //only increase the count if the character is in p  
        //the count >= 0 indicate it was original in the hash, cuz it won't go below 0  
        if (right - left == p.length() && hash[s.charAt(left++)]++ >= 0) count++;  
    }  
    return list;  
}

这个代码上的改动很小, 就是把里面的循环换成一个 if 了(反正也只可能有一种情况). 而且他的 comment 跟我的解释基本是差不多的;

这个是当时加了 log 用来 debug 的代码版本:

public class Solution {  
    public List<Integer> findAnagrams(String s, String p) { //使用hash table+滑动窗口         
        List<Integer> list = new ArrayList<>();  
        char[] chp = p.toCharArray();   
        char[] chs = s.toCharArray();  
        int count = chp.length;  
        int left = 0;  
        int right = 0;  
        int hash[] = new int[256];  
        for (char c : chp) {  
            hash[c]++;  
        }  
        while (right < chs.length) {  
            Printer.printSeperator();//debug  
            System.out.println("start: ");//debug  
            System.out.println((char) 27 + "[31m" + "left: " + left + ", right: " + right + ", count: " + count + (char) 27 + "[0m");//debug  
            Printer.printSlidingWindow(chs, left, right);//debug  
            for (int i = 0; i < 256; i++) if (hash[i] != 0) System.out.println(((char) i) + " = " + hash[i]);//debug  
            char c = chs[right++];  
            if (hash[c]-- >= 1) count--;  
            while (right - left > chp.length) {  
                char prev = chs[left++];  
                if (hash[prev]++ >= 0) count++;  
            }  
            if (count == 0) {  
                list.add(left);  
            }  
            System.out.println("end: ");//debug  
            System.out.println((char) 27 + "[32m" + "left: " + left + ", right: " + right + ", count: " + count + (char) 27 + "[0m");//debug  
            Printer.printSlidingWindow(chs, left, right);//debug  
            for (int i = 0; i < 256; i++) if (hash[i] != 0) System.out.println(((char) i) + " = " + hash[i]);//debug  
        }  
        return list;  
    }  
}

这个跑出来的 log 看起来理解算法就简单很多了;

Problem Description

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
Difficulty:Easy
Total Accepted:33.2K
Total Submissions:99K
Contributor: Stomach_ache
Companies
amazon
Related Topics
hash table
Similar Questions
Valid Anagram Permutation in String