Hackerrank：夏洛克和字谜（中度在字符串部分）

Question

问题描述：https://www.hackerrank.com/challenges/Sherlock-and-anagrams

谁能告诉我我做错了什么？我的算法是：

1. 输入字符串；STR
2. 生成从length i=1到str.length-2的模式字符串
3. 检查str.substring(i+1)中是否存在模式字符串的字谜

input-string   My OP   Expected OP
ifailuhkqq     2         3

我的代码：

public class SherlockandAnagrams
{
    static int count = 0;

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        generatePairs(sc.next());
        int len = 1;
    }

    public static void generatePairs(String str)
    {
        int len = 1;
        //int i=0;
        while (len < str.length())
        {
            for (int i = 0; i + len <= str.length(); i++)
                findAnagramPairs(str, len, str.substring(i, i + len), i + 1);
            len++;
        }
        System.out.println(count);
    }

    private static void findAnagramPairs(String str, int len, String pattern, int p)
    {
        int i = p;
        while (i + len <= str.length())
        {
            if (checkAnagram(pattern, str.substring(i, i + len)))
            {
                count++;
            }
            i++;
        }
    }

    private static boolean checkAnagram(String pattern, String text)
    {
        if (pattern.length() == 1)
        {
            if (pattern.equals(text))
                return true;
            else
                return false;
        }
        else
        {
            int i = 0;
            int j = pattern.length() - 1;
            while (i < pattern.length())
            {
                if (pattern.charAt(i) == text.charAt(j))
                {
                    i++;
                    j--;
                }
                else
                    return false;
            }
            return true;
        }
    }
}

Answer 1

这个问题的一个更简单的解决方案是:
起始索引为(n,m)且长度为L的anagramic对只能存在，如果存在另一对长度为(n或n-1或n+1,m或m-1或m-1)且长度为l-1(n或n-1或n+1,m或m-1或m-1)的anagramic对。因此，我们可以很容易地将效率从bruteforce降低到一个更有效的解决方案。

一个例子：

        A B C B A A B C A
len 1   A       A A     A //all pairs containing A
len 2   A B   B A         //all pairs that match A B or its reverse
len 3   A B C B A         //all pairs that match A B C or its reverse

或

        A B C B A A B C A
len 1     B   B     B     //all pairs containing B
len 2     B C B     B C   //all pairs that match B C or its reverse
len 3   A B C B A A B C   //all pairs that match A B C or its reverse

set pairs = listAnagrams(input , 1)

int len = 1
while NOT pairs.isEmpty()
    set next_len

    //generate pairs with length len + 1
    for pair p in pairs
        pair left = pair(p.a - len , p.b + len)
        pair right = pair(p.a + len , p.b - len)

        if pairs.contains(left)
            next_len.add(pair(p.a , left.b)
        if pairs.contains(right)
            next_len.add(pair(left.a , p.b)

    pairs = next_len
    ++len