[ 问题: ]

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.

[ 解法1: ]

先把有效的字母、数字准备好，然后遍历目标字符串，有效的字符放入buffer。

再比較buffer中的字符串和反转后的字符串，假设同样那就是回文。否则不是回文。

点评：这个解法能够被系统accept，但调用了太多api，性能一般。

public class Solution {

	public boolean isPalindrome(String s) {

		StringBuilder buffer = new StringBuilder();

		String tempStr = "abcdefghijklmnopqrstuvwxyz0123456789";

		char[] cArr = s.toCharArray();

		for (int i = 0; i < cArr.length; i++) {

			if (tempStr.contains(String.valueOf(cArr[i]).toLowerCase())) {

				buffer.append(String.valueOf(cArr[i]).toLowerCase());

			}

		}

		String currentStr = buffer.toString();

		String reverseStr = buffer.reverse().toString();

		if (currentStr.equals(reverseStr)) {

			return true;

		}

		return false;

	}

}

[ 解法2: ]

採用二分法，一个指针从左边遍历，一个从右边遍历，跳过非字母和非数字，当遍历到中点依旧同样那就是回文

点评：代码清晰。性能较好。

public class Solution {

	/**

	 * 推断是否是回文

	 *

	 * @param String str

	 * @return boolean true(is palindrome)/false(is not palindrome)

	 */

	public boolean isPalindrome(String s) {

		if (s == null) {

			return false;

		}

		int i = 0;

		int j = s.length() - 1;

		while (i < j) {

			if (!isAlphanumeric(s.charAt(i))) {

				i++;

				continue;

			}

			if (!isAlphanumeric(s.charAt(j))) {

				j--;

				continue;

			}

			if(Character.toLowerCase(s.charAt(i)) == Character.toLowerCase(s.charAt(j))){

				i++;

				j--;

				continue;

			}

			return false;

		}

		return true;

	}

	/**

	 * 推断是否是字母或数字

	 *

	 * @param char character

	 * @return boolean true(is alphanumeric) / false(is not alphanumeric)

	 */

	public boolean isAlphanumeric(char c) {

		if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')) {

			return true;

		}

		return false;

	}

}