How to check if String is a Palindrome?

Technology CommunityCategory: StringsHow to check if String is a Palindrome?
VietMX Staff asked 3 years ago

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.

Complexity Analysis

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.

Implementation

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());
}