Check if given string is palindrome or not

Problem

Write an algorithm to find Whether Given String is palindrome or Not.

Definition

[Palindrome Definition](/gk/algorithms/palindrome-definition)

Examples

Example 1:

Input: str = "malayalam"
Output: true

Example 2:

Input: str = "abc"
Output: false

Solution

Method 1 - Recursion

Algorithm

• If the first and last characters don't match, return false (not a palindrome).
• If they match, remove the first and last characters and call the function recursively with the remaining substring. This continues until the entire string is checked.

Code

Java

public Boolean isPalindrome(String s) {
	if (s.length()<2) {
		return true;
	}

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

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(n) assuming recursion stack

Method 2 - Using 2 Pointer Approach

Start with 2 iterators at the start and the end till they meet in middle, and check each character. If they don't match, we return false. If we reached end of loop, we return true.

Here is the video explanation: <div class="youtube-embed"><iframe src="https://www.youtube.com/embed/b-Utno_wa1w" frameborder="0" allowfullscreen></iframe></div>

Code

Java

public boolean isPalindrome(String s) {
	int left = 0;
	int right = str.length() - 1;

	while (left < right) {
		if (s.charAt(left) != s.charAt(right)) {
			return false;
		}

		left++;
		right--;
	}

	return true;
}

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1)

Method 3 - Reversing the string

Code

Java

public boolean isPalindrome(String str) {
	StringBuilder reversed = new StringBuilder(str).reverse();
	return str.equals(reversed.toString());
}

Complexity

• ⏰ Time complexity: O(n) as equals method will compare 2 strings char by char
• 🧺 Space complexity: O(n), for creating reversed string