FindAllAnagramsInAString2 [source code]

public class FindAllAnagramsInAString2 {
static
/******************************************************************************/
public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] counts = new int[26];
        Arrays.fill(counts, -1);
        char[] chs = s.toCharArray(), chp = p.toCharArray();
        int lenS = chs.length, lenP = chp.length;
        int targetSum = 0;
        for (int i = 0; i < lenP; i++) {
            if (counts[chp[i] - 'a'] < 0) {
                counts[chp[i] - 'a'] = (int) Math.pow(i + 1, 2);
            } else {
                counts[chp[i] - 'a'] += Math.pow(i + 1, 2);
            }
            targetSum += Math.pow(i + 1, 2);
        }
        int sum = 0;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < lenS; i++) {
            for (int j = 0; j < lenP; j++) {
                if (i + j >= lenS) {
                    sum = 0;
                    i = lenS;
                    break;
                }
                sum += counts[chs[i + j] - 'a'];
            }
            if (sum == targetSum) res.add(i);
            sum = 0;
        }
        return res;
    }
}
/******************************************************************************/

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

这个是刚开始的一个思路, 想的太复杂了, 这个算法在 p 里面有重复的时候是有问题的, 就先放在这里, 以后有空看看怎么改;

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