网站开发工作内容seo学途论坛网

一、需求

• 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

• 说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

输入: "race a car"
输出: false

二、字符串遍历

2.1  思路分析

1. 遍历字符串，将字符串中的数字，大小写字母一律转换成大写字母，存储到一个新的字符串中；
2. 对这个新的字符串反转，比较这两个字符串是否相同即可；
3. 在代码实现2中，我们通过使用相关api对代码实现1进行简化；

2.2  代码实现1

class Solution {public boolean isPalindrome(String s) {StringBuilder sb = new StringBuilder();for(int i = 0; i < s.length(); i++) {if(s.charAt(i) >= '0' && s.charAt(i) <= '9') {sb.append(s.charAt(i));} else if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z') {sb.append((char)(s.charAt(i) - 32));} else if(s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') {sb.append(s.charAt(i));}}String s1 = sb.toString();String s2 = new StringBuilder(s1).reverse().toString();return s1.equals(s2);}
}

2.3  代码实现2

class Solution {public boolean isPalindrome(String s) {StringBuilder sb = new StringBuilder();for(int i = 0; i < s.length(); i++) {if(Character.isLetterOrDigit(s.charAt(i))) {sb.append(Character.toUpperCase(s.charAt(i)));}}String s1 = new StringBuilder(sb).reverse().toString();String s2 = sb.toString();return s1.equals(s2);}
}

2.4  复杂度分析

• 时间复杂度为O(N)；
• 空间复杂度为O(N)；

三、双指针法

3.1  思路分析

1. 如方法2中所说，若串非空，我们得到只含有字母及数字的字符串后，要验证该字符串是否为回文串；
2. 采用双指针，分别指向字符串的首尾，并向中间靠拢，当两个指针相遇或者相越过时，即可判断为回文串；

3.2  代码实现

class Solution {public boolean isPalindrome(String s) {StringBuilder sb = new StringBuilder();for(int i = 0; i < s.length(); i++) {if(Character.isLetterOrDigit(s.charAt(i))) {sb.append(Character.toUpperCase(s.charAt(i)));}}s = sb.toString();int begin = 0, end = s.length() - 1;while(begin < end) {if(s.charAt(begin) == s.charAt(end)) {begin++;end--;} else {return false;}}return true;}
}

3.3  复杂度分析

• 时间复杂度为O(N)；
• 空间复杂度为O(N)；

四、双指针优化

4.1  思路分析

1. 在方法2的基础上，我们可以原地操作，即将双指针在原字符串上遍历，需要注意的是指针移动时，要略过非数字及非字母字符；

4.2  代码实现

class Solution {public boolean isPalindrome(String s) {int begin = 0, end = s.length() - 1;while(begin < end) {while(begin < end && !Character.isLetterOrDigit(s.charAt(begin))) {begin++;}while(begin < end && !Character.isLetterOrDigit(s.charAt(end))) {end--;}if(Character.toUpperCase(s.charAt(begin)) != Character.toUpperCase(s.charAt(end))) {return false;}begin++;end--;}return true;}
}

4.3  复杂度分析

• 时间复杂度为O(N)；
• 空间复杂度为O(1)；

五、学习地址

作者：LeetCode-Solution

链接：https://leetcode-cn.com/problems/valid-palindrome/solution/yan-zheng-hui-wen-chuan-by-leetcode-solution/