[LeetCode] 125. Valid Palindrome

轉自LeetCode

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

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not 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>

這題是在處理 palindrom，但和找 Longest Palindromic Substring 有幾點不一樣

1. 不用算長度
2. input 有非字母的字元，像是空白、逗號等

解法不難，概念如下

• 兩個 pointer，一個從前面開始，一個從後面開始

• 遇到不是字母數字，就不要處理

• 字母都轉成小寫再比對

• 一旦有不一樣的，就回傳 false

code 如下

C++

	class Solution {
	public:
	bool isPalindrome(string s) {
	int left = 0, right = s.length() - 1;
	while(left < right) {
	//> skip non-alphanumeric characters
	while(left < right && !isalnum(s[left])) {
	++left;
	}
	while(left < right && !isalnum(s[right])) {
	--right;
	}
	if(left < right) {
	//> check characters are equal or not
	//>> method 1
	//if(((s[left] + 32 - 'a') % 32) != ((s[right] + 32 - 'a') % 32)) {
	// return false;
	//}
	//>> method 2
	if(toupper(s[left]) != toupper(s[right])) {
	return false;
	}
	++left;
	--right;
	}
	}
	return true;
	}
	};

view raw palindromeString.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public boolean isPalindrome(String s) {
	int left = 0, right = s.length() - 1;
	while(left < right) {
	while(left < right && !Character.isLetterOrDigit(s.charAt(left))) {
	++left;
	}
	while(left < right && !Character.isLetterOrDigit(s.charAt(right))) {
	--right;
	}
	if(left < right) {
	if(Character.toUpperCase(s.charAt(left)) != Character.toUpperCase(s.charAt(right))) {
	return false;
	}
	++left;
	--right;
	}
	}
	return true;
	}
	}

view raw palindromeString.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun isPalindrome(s: String): Boolean {
	var left = 0
	var right = s.lastIndex
	while (left < right) {
	while(left < right && !s[left].isLetterOrDigit()) {
	++left
	}
	while(left < right && !s[right].isLetterOrDigit()) {
	--right
	}
	if (left < right && !s[left].equals(s[right], true)) {
	return false
	}
	++left
	--right
	}
	return true
	}
	}

view raw valid_palindrome.kt hosted with ❤ by GitHub