CODEWITHSUNDEEP
javarecursion
user8894938
user8894938

Reputation:

Efficient way to get palindrome using recursion

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?

Upvotes: 1

Views: 503

Answers (1)

Kayaman
Kayaman

Reputation: 73548

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.

Upvotes: 3

Related Questions