当前位置:网站首页>【LeetCode】5. Valid Palindrome·有效回文
【LeetCode】5. Valid Palindrome·有效回文
2022-07-05 23:08:00 【AQin1012】
题目描述
英文版描述
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise.
英文版地址
https://leetcode.com/problems/valid-palindrome/https://leetcode.com/problems/valid-palindrome/
中文版描述
给定一个字符串 s ,验证 s 是否是 回文串 ,只考虑字母和数字字符,可以忽略字母的大小写。 本题中,将空字符串定义为有效的 回文串 。
示例 1: 输入: s = "A man, a plan, a canal: Panama" 输出: true 解释:"amanaplanacanalpanama" 是回文串 示例 2: 输入: s = "race a car" 输出: false 解释:"raceacar" 不是回文串
Constraints·提示:
1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成
中文版地址
https://leetcode.cn/problems/XltzEq/https://leetcode.cn/problems/XltzEq/
解题思路
先全部转小写字母(题目要求忽略大小写)然后先去除除了字母和数字的字符,首尾依次比较
解题方法
俺这版
class Solution {
public static boolean isPalindrome(String s) {
String s1 = s.toLowerCase().replaceAll("[^a-z|0-9]", "");
int length = s1.length();
for (int i = 0; i < length; i++) {
int j = length - i - 1;
if(j <= i){
break;
}
char c1 = s1.charAt(i);
char c2 = s1.charAt(j);
if (c1 != c2) {
return false;
}
}
return true;
}
}
官方版
筛选+比较
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());
}
}
双指针法
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));
}
}
int n = sgood.length();
int left = 0, right = n - 1;
while (left < right) {
if (Character.toLowerCase(sgood.charAt(left)) != Character.toLowerCase(sgood.charAt(right))) {
return false;
}
++left;
--right;
}
return true;
}
}
总结
我的方法看似和官方提供的双指针法很像,但是执行时间和内存消耗都要更多,特别是执行时间 》〉果然没有对比就没有伤害(╯﹏╰)
刚开始我以为是后面比较时我用的String,官方用的StringBuffer,StringBuffer比String遍历快的原因,于是我把我代码中正则匹配后的的字符串赋值给了一个StringBuffer,然后使用该StringBuffer进行遍历,然并卵(-。-; 更慢了。。。
But!当我把正则匹配换成了Character.isLetterOrDigit(),速度蹿蹿的~~
原来字符串的正则匹配这么慢,欢迎知道原因的同学评论区踢我哦*〜(ゝ。∂)
边栏推荐
- asp.net弹出层实例
- 数学公式截图识别神器Mathpix无限使用教程
- TypeError: this. getOptions is not a function
- The PNG image is normal when LabVIEW is opened, and the full black image is obtained when Photoshop is opened
- LabVIEW打开PNG 图像正常而 Photoshop打开得到全黑的图像
- Déterminer si un arbre binaire est un arbre binaire complet
- 进击的技术er——自动化
- MySQL (1) -- related concepts, SQL classification, and simple operations
- Pyqt control part (I)
- Hainan Nuanshen tea recruits warmhearted people: recruitment of the product experience recommender of Nuanshen multi bubble honey orchid single cluster
猜你喜欢
2022 G3 boiler water treatment simulation examination and G3 boiler water treatment simulation examination question bank
3:第一章:认识JVM规范2:JVM规范,简介;
Southeast Asia e-commerce guide, how do sellers layout the Southeast Asia market?
Three. JS VR house viewing
The method and principle of viewing the last modification time of the web page
TVS管和ESD管的技術指標和選型指南-嘉立創推薦
Neural structured learning - Part 2: training with natural graphs
Scala concurrent programming (II) akka
Data type, variable declaration, global variable and i/o mapping of PLC programming basis (CoDeSys)
Technical specifications and model selection guidelines for TVs tubes and ESD tubes - recommended by jialichuang
随机推荐
asp. Net pop-up layer instance
Spécifications techniques et lignes directrices pour la sélection des tubes TVS et ESD - Recommandation de jialichuang
Multi sensor fusion of imu/ optical mouse / wheel encoder (nonlinear Kalman filter)
Brushless drive design -- on MOS drive circuit
LabVIEW打开PNG 图像正常而 Photoshop打开得到全黑的图像
Idea rundashboard window configuration
The interface of grafana tool displays an error, incluxdb error
Solution to the packaging problem of asyncsocket long connecting rod
Three.js-01 入门
[original] what is the core of programmer team management?
Neural structured learning - Part 2: training with natural graphs
How to enable relationship view in phpMyAdmin - how to enable relationship view in phpMyAdmin
Use of shell:for loop
What is the process of building a website
Multi camera stereo calibration
视频标准二三事
C# Linq Demo
Southeast Asia e-commerce guide, how do sellers layout the Southeast Asia market?
Creative mode 1 - single case mode
3:第一章:认识JVM规范2:JVM规范,简介;