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）。