Efficient way for finding Shortest Palindrome from Arraylist of strings

Question

I am trying to solve this problem in java. I have an arraylist of palindromic strings. I have to find the shortest palindrome string out of the given array list. I have solved the question but was looking at getting feedback on my code and also how I can try to make the code more efficient/better.

Here is the code what I have tried.

In this case, size would be 3, since that is the length of the smallest palindromic string.

import java.util.ArrayList;
class ShortestPalindrome {
    public static int isShortestPalindrome(ArrayList<String> list) {
        int smallest = list.get(0).length();
        boolean ret = false;
        for (String element : list) {
            ret = isPalindrome(element);
            if (ret) {
                if (element.length() < smallest) 
                    smallest = element.length();                
            }
        }
        return smallest;
    }

    private static boolean isPalindrome(String input) {
        String str = "";
        boolean result = false;

        if (input.length() == 1 || input.length() == 0)
            return true;

        if (input.charAt(0) != input.charAt(input.length() - 1))
            return false;
        StringBuilder sb = new StringBuilder(input.toLowerCase());
        str = sb.reverse().toString();
        if (input.equals(str)) {
            result = true;
        }
        return result;
    }

    public static void main(String[] args) {
        ArrayList<String> array = new ArrayList<String>();
        array.add("malayam");
        array.add("aba");
        array.add("abcdeyugugi");
        array.add("nitin");
        int size = isShortestPalindrome(array);
        System.out.println("Shortest length of string in list:" + size);
    }
}

Answer 1

I have a couple of comments regarding your code:

1. In general - if you break your problem to smaller parts, there are efficient solutions all around.
2. As @AKSW mentioned in his comment, if - in any case - we have to check each string's length, it's better to do it in the beginning - so we don't run the relatively expensive method isPalindrome() with irrelevant strings.
   (Just notice I override the given list with the sorted one, even though initializing a new sorted list is trivial)
3. The main improvement that I made is in the isPalindrome() method:
   • Reversing a string of length n takes n time and additional n space. Comparing the two takes also n time.
     Overall: 2n time, n space
   • Comparing each two matching characters (from the beginning and from the end) takes 2 additional space (for the integers) and approximately n/2 time.
     Overall: n/2 time, 2 space

Obviously when using limits for complexity calculations, the time complexities are both the same - O(n) - but the second solution is still 4 times cheaper and cost a negligible amount of space.

Therefore I believe this is the most efficient way to achieve your test:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class ShortestPalindrome {
    public static int isShortestPalindrome(ArrayList<String> list) {
        // Sorts the given ArrayList by length
        Collections.sort(list, Comparator.comparingInt(String::length));
        for (String element : list) {
            if(isPalindrome(element)) {
                return element.length();
            }
        }
        return -1; // If there is no palindrome in the given array
    }

    private static boolean isPalindrome(String input) {
        String lowerCased = input.toLowerCase();
        int pre = 0;
        int end = lowerCased.length() - 1;
        while (end > pre) {
            if (lowerCased.charAt(pre) != lowerCased.charAt(end))
                return false;
            pre ++;
            end --;
        }
        return true;
    }

    public static void main(String[] args) {
        ArrayList<String> array = new ArrayList<>(Arrays.asList("malayam", "aba", "abcdeyugugi", "nitin"));
        int size = isShortestPalindrome(array);
        System.out.println("Shortest length of string in list: " + size);
    }
}

Edit: I've tested this algorithm with the following list. Sorting the list before checking for palindromes reduces run time in 50%.

"malayam", "aba", "abcdeyugugi", "nitin", "sadjsaudifjksdfjds", "sadjsaudifjksdfjdssadjsaudifjksdfjds", "sadjsaudifjksdfjdssadjsaudifjksdfjdssadjsaudifjksdfjds", "a"