一、leetcode算法
1、验证回文串
1.1、题目
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: “A man, a plan, a canal: Panama”
输出: true
解释：“amanaplanacanalpanama” 是回文串
示例 2:
输入: “race a car”
输出: false
解释：“raceacar” 不是回文串
1.2、思路
思路一：此题我们可以将字符串进行一次遍历，将其中的字母和数字字符拿出来放到另一个字符串中，然后我们只需要判断另一个字符串是否是回文串即可。
1.3、答案
class Solution { public boolean isPalindrome(String s) { StringBuffer sgood = new StringBuffer(); int length = s.length(); for(int i = 0; i < length; i++){ char ch = s.charAt(i); if(Character.isLetterOrDigit(ch)){ sgood.append(Character.toLowerCase(ch)); } } StringBuffer sgood_rev = new StringBuffer(sgood).reverse(); return sgood.toString().equals(sgood_rev.toString()); } }
复杂度分析
时间复杂度：O(|s|)，其中 |s| 是字符串 s 的长度。
空间复杂度：O(|s|)。由于我们需要将所有的字母和数字字符存放在另一个字符串中，在最坏情况下，新的字符串sgood 与原字符串 s 完全相同，因此需要使用 O(|s|)的空间。
