题目:
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
解释:"amanaplanacanalpanama" 是回文串
示例 2:
输入: "race a car"
输出: false
解释:"raceacar" 不是回文串
提示:
1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/valid-palindrome
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
一、双指针
利用两个指针left和right分别指向字符串的首部和尾部,遍历并比较两个指针所指位置的字符是否相等即可。
1.先将字符串中的所有字符转换成小写字符;
2.循环字符串,判断其两个指针所指字符是否为数字或小写字符;
3.如果left,right指针对应字符不是数字和字母的,则让对应指针指向下一个位置,如果是,则判断是否一致,不一致返回false,一致返回true。
代码:
1 class Solution { 2 public boolean isPalindrome(String s) { 3 String l = s.toLowerCase(); 4 int n = l.length(); 5 for(int i = 0, j = n-1; i < j;){ 6 char left = l.charAt(i); 7 char right = l.charAt(j); 8 if(!(Character.isDigit(left) || Character.isLowerCase(left))){ 9 i++; 10 continue; 11 }else if(!(Character.isDigit(right) || Character.isLowerCase(right))){ 12 j--; 13 continue; 14 } 15 if(left != right){ 16 return false; 17 } 18 i++; 19 j--; 20 } 21 return true; 22 } 23 }
二、利用StringBuffer的reverse方法来判断
1.先逐个字符读取到StringBuffer,过滤不需要字符,并将大写字符转换小写;
2.然后使用StringBuffer的reverse()方法翻转字符串,判断是否相等。
代码:
三、利用栈
将所有字母数字全部入栈,再全部出栈后就能得到反转,将入栈的内容与出栈的内容对比,完全相等那就是回文串。
代码:
1 class Solution { 2 public boolean isPalindrome(String s) { 3 s = s.toLowerCase(); 4 Stack stack = new Stack(); 5 //保存入栈的内容 6 StringBuilder m1 = new StringBuilder(); 7 //保存出栈的内容 8 StringBuilder m2 = new StringBuilder(); 9 int n = s.length(); 10 for(int i = 0; i < n; i++){ 11 char c = s.charAt(i); 12 if(Character.isLetterOrDigit(c)){ 13 stack.push(c); 14 m1.append(c); 15 } 16 } 17 while(!stack.empty()){ 18 m2.append(stack.pop()); 19 } 20 if(m1.toString().equals(m2.toString())){ 21 return true; 22 }else{ 23 return false; 24 } 25 } 26 }