A palindrome is a word, phrase, number or other sequence of units that can be read the same way in either direction. You can check if a string is a palindrome by comparing it to the reverse of itself either using simple loop or recursion.
The time complexity is O(n/2)
that is still O(n)
. We doing n
comparisons, where n = s.length()
. Each comparison takes O(1)
time, as it is a single character comparison. You can cut the complexity of the function in half by stopping at i == (s.length() / 2)+1
. It is not relevant in Big O terms, but it is still a pretty decent gain. Loop approach has constant space complexity O(1)
as we not allocating any new memory. Reverse string approach needs O(n)
additional memory to create a reversed copy of a string. Recursion approach has O(n)
space complexity due call stack.
Loop:
boolean isPalindrome(String str) {
int n = str.length();
for( int i = 0; i < n/2; i++ )
if (str.charAt(i) != str.charAt(n-i-1)) return false;
return true;
}
Recursion:
private boolean isPalindrome(String s) {
int length = s.length();
if (length < 2) return true;
return s.charAt(0) != s.charAt(length - 1) ? false :
isPalindrome(s.substring(1, length - 1));
}
You may want to solve the problem by inverting the original string in a whole but note the space complexity will be worst than for the loop solution (O(n)
instead of O(1)
):
public static boolean isPalindrome(String str) {
return str.equals(new StringBuilder(str).reverse().toString());
}