FindAllAnagramsInAString [source code]

public class FindAllAnagramsInAString {
static
/******************************************************************************/
public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        char[] chs = s.toCharArray(), chp = p.toCharArray();
        List<Integer> res = new ArrayList<>();
        int lenS = chs.length, lenP = chp.length;
        for (int i = 0; i < lenS; i++) {
            if (isAnagram(chs, chp, i)) {
                res.add(i);
            }
        }
        return res;
    }

    public boolean isAnagram(char[] chs, char[] chp, int start) {
        int lenS = chs.length, lenP = chp.length;
        if (start + lenP > lenS) return false;
        int[] counts = new int[26];
        for (int i = 0; i < lenP; i++) {
            counts[chs[i + start] - 'a']++;
            counts[chp[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) if (counts[i] > 0) return false;
        return true;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        FindAllAnagramsInAString.Solution tester = new FindAllAnagramsInAString.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));
        }
    }
}

这个题目的暴力算法还是很简单的, 直接就是挨个找就行了, 最后的复杂度是O(M*(N^2)).

这个题目要考虑的一点是两个 string 如果有 duplicate 怎么办? 有 duplicate 好像做起来麻烦不少;

这个题目一开始想的太复杂了, 其实思路非常简单. 之前那个想复杂了但是不对的代码扔在ver2了;
先做一个粗糙解, 做一个 i 需要 backup 的解; 后面想想能不能类似 KMP 那样跳子;

我这里判断每个 window 里面的是 anagram 的方法其实是直接用 char 值加起来求和相等就可以, 求和的作用就是为了消除顺序的影响. 不过不能直接求和, 因为比如0 1 2 3, 那么0 3的和跟1 2的和就是相等的. 所以我的做法是先平方再求和. 不过没有想到居然有人专门预料到了有人会这么写, 直接专门搞了一个 case, break 这个算法, 这个 case 的核心点就是"buq" 和"ncw" 两个的平方求和是相等的. 我就干脆换成了三次方. 不过感觉过一段时间还是会有蛋疼的人加 case 来 break 这个.
要么更好的方法是换一个更隐秘的算法来计算这个和, 要么就是换一个思路. 我认为只要保证 window 里面两个 string 的 constituents 相同, 好像就可以了;

果然, 三次方还是有问题, 这帮比故意一个 case, 很长的一个 string, 全都是'a', 让你超时;

那我试试+1之后平方; //+1好像还是跑不过 buq 这个 case; 算了, 直接 count 算了. count 也是O(N) 的速度, 何苦呢;

for (int i = 0; i < lenP; i++) {  
    sum1 += Math.pow(chs[start + i] + 1, 2);  
    sum2 += Math.pow(chp[i] + 1, 2);  
}

这个是当时计算的代码, 留个存根;

吭哧吭哧做完了, 结果最后的速度惨不忍睹, 不知道哪里出问题了: 710ms (10%).

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