一、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|)的空间。