一、题目
1、算法题目
“给定一个字符串，验证它是否是回文串。”
题目链接：
来源：力扣（LeetCode）
链接： 125. 验证回文串
2、题目描述
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明： 本题中，我们将空字符串定义为有效的回文串。
示例 1： 输入: "A man, a plan, a canal: Panama" 输出: true 解释： "amanaplanacanalpanama" 是回文串 复制代码
示例 2： 输入: "race a car" 输出: false 解释： "raceacar" 不是回文串 复制代码
二、解题
1、思路分析
这道题是考查对于常用字符串中API的使用。
最简单的方法是对字符串s进行一次遍历，将其中的字母和数字字符进行保留，保存在另一个字符串sgood中。
这样就只需要判断sgood是否是一个普通的字符串即可。
判断sgood是否是一个回文串也很简单，使用API逆序字符串，判断这两个字符串是否相同即可。
2、代码实现
代码参考：
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()); } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(|s|)
其中|s|是字符串s的长度。
空间复杂度： O(|s|)
其中|s|是字符串s的长度，由于需要将所有的字母和数字存放到一个字符串中，在最坏的情况下，得到的新新字符串和原字符串完全相同，因此需要O(|s|)的空间。
三、总结
这道题还可以使用双指针。
在开始的时候两个指针分别指向sgood的两侧，随后不断向中间移动。
每移动一步，判断这两个指针指向的字符是否相同，当这两个指针相遇时，说明sgood是回文串。
