Miljan Miljan - 7 days ago 6
Java Question

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 ?

Answer

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.