Pair Palindrome

Question

I have this code to find all pairs of string to form a palindrome. e.g) D: { AB, DEEDBA } => AB + DEEDBA -> YES and will be returned. Another example, { NONE, XENON } => NONE + XENON = > YES.

What would be running time of this ?

    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

I'm going to take a few guesses here as I don't have much experience with Java.

First, isPalindrome is O(N) with the size of suffix string. Add operation to 'pairs' would probably be O(1).

Then, we have the for loop, it's O(N) with the length of r. Getting a substring I'd think is O(M) with the size of the substring. Checking if a hashmap contains a certain key, with a perfect hash function would be (IIRC) O(1), in your case we can assume O(lgN) (possibly). So, first for loop has O(NMlgK), where K is your hash table size, N is r's length and M is substring's length.

Finally we have the outmost for loop, it runs for each string in the string list, so that's O(N). Then, we reverse each of them. So for each of these strings we have another O(N) operation inside, with the other loop being O(NMlgK). So, overall complexity is O(L(N + NMlgK)), where L is the amount of strings you have. But, it'd reduce to O(LNMlgK). I'd like if someone verified or corrected my mistakes.

EDIT: Actually, substring length will at most be N, as the length of the entire string, so M is actually N. Now I'd probably say it's O(LNlgK).