Problem

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Palindrome Definition

Examples

Example 1:

1
2
3
4
5

Input:
s = "A man, a plan, a canal: Panama"
Output:
 true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

1
2
3
4
5

Input:
s = "race a car"
Output:
 false
Explanation: "raceacar" is not a palindrome.

Example 3:

1
2
3
4
5
6

Input:
s = " "
Output:
 true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Note

Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome.

Solution

From start and end loop though the string, i.e., char array. If it is not alpha or number, increase or decrease pointers. Compare the alpha and numeric characters. The solution below is pretty straightforward.

We have seen similar problem - Check if given string is palindrome or not.

Method 1 - Using 2 Pointers and removing non-alphanumeric chars

Some interviewers may not allow above.

Code

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

public static boolean isValidPalindrome(String s) {

	s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();

	for (int i = 0; i<s.length(); i++) {
		if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
			return false;
		}
	}

	return true;
}

Complexity

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

Method 2 - Using 2 pointers after lowercasing the string

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

public boolean isPalindrome2(String s) {
	if (s == null || s.isEmpty()) {
		return true;
	}
	s = s.toLowerCase();
	for (int i = 0, j = s.length() - 1; i < j; ) {
		char leftChar = s.charAt(i);
		char rightChar = s.charAt(j);
		if (!isAlphaNum(leftChar)) {
			i++;
			continue;
		}
		if (!isAlphaNum(rightChar)) {
			j--;
			continue;
		}
		if (leftChar != rightChar) {
			return false;
		}
		i++;
		j--;
	}
	return true;
}

public boolean isAlphaNum(char a) {
	if ((a >= 'a' && a<= 'z') || 
		(a >= 'A' && a<= 'Z') || 
		(a >= '0' && a<= '9')) {
		return true;
	} 
	return false;
}

Complexity

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

Method 2 - Using 2 pointers - No shortcuts

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public boolean isPalindrome(String s) {
	if (s == null) {
		return true;
	}
	if (s.length()<2) {
		return true;
	}
	int n = s.length();
	int i = 0; // left pointer
	int j = n - 1; // right pointer

	while (i<j) {
		// note upper bound is r and not n
		// this improves time complexity a bit
		while (i < j && !isAlphaNum(s.charAt(i))) {
			i++;
		}
	
		while (j > i && !isAlphaNum(s.charAt(j))) {
			j--;
		}

		if (i >= j)
			break;

		if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
			return false;
		}

		i++;
		j--;
	}
	return true;
}

Complexity

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

Method 4 - Using Stack

This solution removes the special characters first.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

public boolean isPalindrome(String s) {
	// a shortcut
	s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();

	int len = s.length();

	if (len < 2) {
		return true;
	}

	Stack<Character> stack = new Stack<Character>();

	int index = 0;

	while (index < len / 2) {
		stack.push(s.charAt(index));
		index++;
	}

	if (len % 2 == 1) {
		index++;
	}

	while (index < len) {
		if (stack.empty()) {
			return false;
		}
			
		char temp = stack.pop();

		if (s.charAt(index) != temp) {
			return false;
		} else {
			index++;
		}

	}

	return true;
}

Complexity

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