Search code examples
javarecursionpalindrome

substring() method in a Palindrome


In a well know recursion isPalindrome method

  public static boolean isPalindrome(String s){

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

        if(s.charAt(0) == s.charAt(s.length()-1))
            return isPalindrome(s.substring(1, s.length()-1));

            return false;
        }
 }

there is one line that I dont quite understand. If, for example we pass the string anna to the isPalindrome method, what does this line of code

return isPalindrome(s.substring(1, s.length()-1)); 

do to the string when s has a value of nn ?

In my understanding number 1 (index 1) is for second letter n, and s.length()-1 is equal 2-1 = 1, but not including that index position, so that must be index 0 ??

Does it return an empty string or something else ?


Solution

  • When the value of s is nn, as we step through the statements, this will happen:

    • s.length() is 2, so the first if condition doesn't match
    • s.charAt(0) is n, and s.charAt(1) is n, so the second if matches
    • Return the result of isPalindrome with parameter s.substring(1, 1), which is the text range from position 1 until before the position 1, in other words, an empty string
    • In the recursive call with empty string as input, isPalindrome will match the first condition on length, and return true

    For the record, this is a very inefficient way to check a palindrome in Java, because substring creates new strings, which is slow. A more efficient recursive solution is possible by adding start and end index parameters, and moving them inward, until their difference becomes 0 or 1.