对回文

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)，后缀字符串的大小。添加操作到 'pairs' 可能是 O(1).

然后，我们有for循环，它是O(N)，长度为r。获取子字符串我认为是 O(M) 与子字符串的大小。检查哈希图是否包含某个键，具有完美的哈希函数将是 (IIRC) O(1)，在您的情况下我们可以假设 O(lgN)（可能）。所以，第一个 for 循环有 O(NMlgK)，其中 K 是你的散列 table 大小，N 是 r 的长度，M 是子字符串的长度。

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

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

对回文

Pair Palindrome

java

hash

palindrome