Hackerrank：Sherlock和Anagrams（在Strings部分的中等） [英] Hackerrank: Sherlock and Anagrams(Moderate under Strings section)

问题描述

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

有人可以告诉我我做错了什么？我的算法是：

Can somebody please tell me what am I doing wrong? My algorithm is:

1. 输入字符串; str


2. 生成从长度为i = 1到str.length-2的模式字符串


3. 检查str.substring中是否存在模式字符串的描述（ i + 1）

以下是不通过的测试用例：

Below are the test cases which are NOT passing :

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;
        }
    }
}

推荐答案

这个问题的一个更简单的解决方案如下：

一个与（n，m）和长度的起始索引的anagramic对 l 只能在（n或n）的长度 l - 1 - 1或n + 1，m或m-1或m-1）存在。因此，我们可以轻松地将效率从强力降低到更有效的解决方案。

A simpler solution to the problem would be the following:
An anagramic pair with starting-indices at (n , m) and length l can only exist, if another pair with length l - 1 at (n or n - 1 or n + 1 , m or m - 1 or m - 1) exists. Thus we can easily reduce efficiency from bruteforce to a more efficient solution.

一个例子：

        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

同样适用于任何其他长度 l ，它的长度为 l + 1 的匹配对。通常，一对长度 l + 1 只存在，如果两对（a，b）和<$存在长度 l 的c $ c>（c，d），这样 a = c - code>和 b = d + l 或 a = c + l 和 b = d-l 存在

The same applies to any other pair of length l and it's matching pairs with length l + 1. In general, a pair of length l + 1 only exists, if two pairs (a , b) and (c , d) of length l exists, such that either a = c - l and b = d + l or a = c + l and b = d - l exist.

在伪代码中，这将如下所示：

In pseudocode this would look like this:

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

这篇关于Hackerrank：Sherlock和Anagrams（在Strings部分的中等）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！