Pair Palindrome

Question

我有这段代码找到所有的字符串对形成回文。例如）D：{AB，DEEDBA} => AB + DEEDBA - > YES并将被返回。另一个例子{NONE，XENON} => NONE + XENON => YES。

这会是什么运行时间？

public static List<List<String>> pairPalindrome(List<String> D) { 
    List<List<String>> pairs = new LinkedList<>(); 
    Set<String> set = new HashSet<>(); 
    for (String s : D) { 
     set.add(s); 
    } 
    for (String s : D) { 
     String r = reverse(s); 
     for (int i = 0; i <= r.length(); i++) { 
      String prefix = r.substring(0, i); 
      if (set.contains(prefix)) { 
       String suffix = r.substring(i); 
       if (isPalindrom(suffix)) { 
        pairs.add(Arrays.asList(s, prefix)); 
       } 
      } 
     } 
    } 
    return pairs; 
} 
private static boolean isPalindrom(String s) { 
     int i = 0; 
     int j = s.length() - 1; 
     char[] c = s.toCharArray(); 
     while (i < j) { 
      if (c[i] != c[j]) { 
       return false; 
      } 
      i++; 
      j--; 
     } 
     return true; 
    } 

private static String reverse(String s) { 
    char[] c = s.toCharArray(); 
    int i = 0; 
    int j = c.length - 1; 
    while (i < j) { 
     char temp = c[i]; 
     c[i] = c[j]; 
     c[j] = temp; 
     i++; 
     j--; 
    } 
    return new String(c); 
} 

Answer 1

因为我没有太多的Java经验，所以我会在这里进行一些猜测。

首先，isPalindrome是O（N），后缀字符串的大小。将操作添加到“对”可能是O（1）。

然后，我们有for循环，它的长度为r的O（N）。得到一个子串我会认为是O（M）与子串的大小。检查一个hashmap是否包含一个特定的密钥，并且有一个完美的散列函数会是（IIRC）O（1），在你的情况下我们可以假设O（lgN）（可能）。所以，首先for循环有O（NMlgK），其中K是你的哈希表大小，N是r的长度，M是子串的长度。

最后，我们有最外面的for循环，它为字符串列表中的每个字符串运行，所以这是O（N）。然后，我们扭转它们中的每一个。所以对于这些字符串中的每一个，我们都有另一个O（N）操作，另一个循环是O（NMlgK）。因此，总体复杂度是O（L（N + NMlgK）），其中L是您拥有的字符串数量。但是，它会减少到O（LNMlgK）。我想如果有人验证或纠正我的错误。

编辑：实际上，子字符串的长度至多是N，因为整个字符串的长度，所以M实际上是N.现在我可能会说它是O（LNlgK）。