当前位置:网站首页>【LeetCode】5. Valid palindrome
【LeetCode】5. Valid palindrome
2022-07-05 23:34:00 【AQin1012】
Title Description
Description in English
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.
English address
https://leetcode.com/problems/valid-palindrome/https://leetcode.com/problems/valid-palindrome/
Description of Chinese version
Given a string s , verification s Whether it is Palindrome string , Consider only alphabetic and numeric characters , The case of letters can be ignored . In this question , Define an empty string as a valid Palindrome string .
Example 1: Input : s = "A man, a plan, a canal: Panama" Output : true explain :"amanaplanacanalpanama" It's a palindrome string Example 2: Input : s = "race a car" Output : false explain :"raceacar" It's not a palindrome string
Constraints· Tips :
1 <= s.length <= 2 * 105
character string s from ASCII Character composition
Address of Chinese version
https://leetcode.cn/problems/XltzEq/https://leetcode.cn/problems/XltzEq/
Their thinking
First turn all lowercase letters ( The title requires that case be ignored ) Then remove the characters except letters and numbers , Compare first and last
How to solve the problem
My version
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;
}
}
Official edition
Screening + Compare
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());
}
}
Double finger needling
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;
}
}
summary
My method seems to be very similar to the official double pointer method , But the execution time and memory consumption are more , Especially the execution time 》〉 As expected, there is no harm without comparison (╯﹏╰)
At first, I thought it was the one I used in the later comparison String, Official StringBuffer,StringBuffer Than String The reason why traversal is fast , So I assigned the regular matching string in my code to a StringBuffer, And then use that StringBuffer Traversal , But it is of no damn use (-。-; More slowly ...
But! When I replace regular matching with Character.isLetterOrDigit(), The speed is soaring ~~
The regular matching of the original string is so slow , Welcome students who know the reason to kick me in the comment area *〜(ゝ.∂)
边栏推荐
- 进击的技术er——自动化
- orgchart. JS organization chart, presenting structural data in an elegant way
- 2022.6.20-6.26 AI行业周刊(第103期):新的小生命
- idea 连接mysql ,直接贴配置文件的url 比较方便
- Switching power supply buck circuit CCM and DCM working mode
- 3D reconstruction of point cloud
- 【原创】程序员团队管理的核心是什么?
- The interface of grafana tool displays an error, incluxdb error
- Pyqt control part (I)
- MySQL (2) -- simple query, conditional query
猜你喜欢
Go语言实现原理——锁实现原理
保研笔记四 软件工程与计算卷二(8-12章)
Spire.PDF for NET 8.7.2
Non rigid / flexible point cloud ICP registration
98. Verify the binary search tree ●●
How to design API return code (error code)?
CIS benchmark tool Kube bench
Attacking technology Er - Automation
Switching power supply buck circuit CCM and DCM working mode
Technical specifications and model selection guidelines for TVs tubes and ESD tubes - recommended by jialichuang
随机推荐
3: Chapter 1: understanding JVM specification 2: JVM specification, introduction;
《牛客刷verilog》Part III Verilog企业真题
How to improve eloquence
秒杀系统的设计与实现思路
2022.6.20-6.26 AI industry weekly (issue 103): new little life
The maximum happiness of the party
Design and implementation of secsha system
Rasa 3. X learning series -rasa x Community Edition (Free Edition) changes
698. 划分为k个相等的子集 ●●
2: Chapter 1: understanding JVM specification 1: introduction to JVM;
Use of metadata in golang grpc
AsyncSocket长连接棒包装问题解决
MySQL (2) -- simple query, conditional query
如何提升口才
代码农民提高生产力
6-axis and 9-axis IMU attitude estimation
424. 替换后的最长重复字符 ●●
Fiddler Everywhere 3.2.1 Crack
Pyqt control part (I)
ts类型声明declare