Problem

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

Definition

Palindrome Definition

Examples

Example 1:

1
2

Input: str = "malayalam"
Output: true

Example 2:

1
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

1
2
3
4

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