Hackerrank：Sherlock和Anagrams（在Strings部分中等）

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

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

1. 输入字符串; 海峡
2. 生成从长度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

解决问题的更简单方法如下：
如果另一对长度为l - 1 at (n or n - 1 or n + 1 , m or m - 1 or m - 1) ，则只能存在具有(n , m)和长度l起始指数的anagramic对存在。 因此，我们可以轻松地将powershell从低强度降低到更有效的解决方案。

一个例子：

  ABCBAABCA len 1 AAAA //all pairs containing A len 2 ABBA //all pairs that match AB or its reverse len 3 ABCBA //all pairs that match ABC or its reverse 

要么

  ABCBAABCA len 1 BBB //all pairs containing B len 2 BCBBC //all pairs that match BC or its reverse len 3 ABCBAABC //all pairs that match ABC or its reverse 

这同样适用于任何其他长度l和它的匹配对，长度为l + 1 。 通常，如果存在长度为l + 1两对(a , b)和(c , d) ，则存在一对长度l + 1 ，使得a = c - l和b = d + l或a = c + l和b = d - l存在。

在伪代码中，这将是这样的：

 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(pa - len , pb + len) pair right = pair(pa + len , pb - len) if pairs.contains(left) next_len.add(pair(pa , left.b) if pairs.contains(right) next_len.add(pair(left.a , pb) pairs = next_len ++len