Efficient way to get palindrome using recursion

Question

I'm trying to get palindrome using recursion like this, but I found that very costly because It's create new string when I use substring() method, like in my code:

 public static boolean isPalindrome(String s) {
    if (s.length() <= 1)
        return true;
    else if (s.charAt(0) != s.charAt(s.length() - 1))
        return false;
    else return isPalindrome(s.substring(1, s.length() - 1));
}

Is there an alternative way to make it more efficient?

Kayaman · Accepted Answer · 2018-03-12T19:16:32.033

You can pass the full original String and just the indexes to it, it'll be essentially the same thing except without creating so many objects.

public static boolean isPalindrome(String s, int start, int end) {
    if ((end-start) <= 1)
        return true;
    else if (s.charAt(start) != s.charAt(end))
        return false;
    else return isPalindrome(s, start+1, end-1);
}

public static boolean isPalindrome(String s) {
    return isPalindrome(s, 0, s.length()-1);
}

The original code was more efficient back when substring() shared the internal char[] of the String, but that changed. Even then this would've been a better option, since the String objects were still created even though the internal char[] was shared.

Efficient way to get palindrome using recursion

1 Answers1