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 ?
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 matchs.charAt(0)
is n
, and s.charAt(1)
is n
, so the second if
matchesisPalindrome
with parameter s.substring(1, 1)
, which is the text range from position 1 until before the position 1, in other words, an empty stringisPalindrome
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.