【小Y学算法】每日LeetCode打卡——36. 验证回文串
【小Y学算法】每日LeetCode打卡——36. 验证回文串
呆呆敲代码的小Y
发布于 2022-05-10 09:25:15
发布于 2022-05-10 09:25:15
文章被收录于专栏：呆呆敲代码的小Y 公众号
📢前言
请添加图片描述
🚀 算法题 🚀 |
|---|
🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
- 🌲 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
- 🌲 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧🧐！
- 🌲 今天是力扣算法题持续打卡第36天🎈！
🚀 算法题 🚀 |
|---|
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
**说明：**本题中，我们将空字符串定义为有效的回文串。
示例 1：
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串示例 2：
输入: "race a car"
输出: false
解释："raceacar" 不是回文串提示：
- 1 <= s.length <= 2 * 10^5
- 字符串 s 由 ASCII 字符组成
🌻C#方法：双指针
思路解析
利用双指针，从字符串两头往中间遍历并进行比对，跳过非数字或字母项。
代码：
public class Solution {
public bool IsPalindrome(string s)
{
if (s == null)
{
return false;
}
int left = 0;
int right = s.Length - 1;
while (left <= right)
{
var leftElement = char.ToLower(s[left]);
var rightElement = char.ToLower(s[right]);
if ((leftElement >= 'a' && leftElement <= 'z' || leftElement >= '0' && leftElement <= '9') && rightElement >= 'a' && rightElement <= 'z' || rightElement >= '0' && rightElement <= '9')
{
if (leftElement != rightElement)
{
return false;
}
left++;
right--;
}
else if (leftElement >= 'a' && leftElement <= 'z' || leftElement >= '0' && leftElement <= '9')
{
right--;
}
else
{
left++;
}
}
return true;
}
}执行结果
通过
执行用时：212 ms，在所有 C# 提交中击败了31.47%的用户
内存消耗：25.9 MB，在所有 C# 提交中击败了52.99%的用户🌻Java 方法一：筛选 + 判断
思路解析
最简单的方法是对字符串 s 进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串sgood 中。这样我们只需要判断 sgood 是否是一个普通的回文串即可。
判断的方法有两种。第一种是使用语言中的字符串翻转 API 得到 sgood 的逆序字符串 sgood_rev，只要这两个字符串相同，那么 sgood 就是回文串。
代码：
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());
}
}执行结果
通过
执行用时：5 ms，在所有 Java 提交中击败了32.73%的用户
内存消耗：38.4 MB，在所有 Java 提交中击败了76.12%的用户复杂度分析
时间复杂度：O( |s| ),其中 ∣s∣ 是字符串 s 的长度。
空间复杂度：O( |s| )，由于我们需要将所有的字母和数字字符存放在另一个字符串中，在最坏情况下，新的字符串sgood 与原字符串 s 完全相同，因此需要使用 O(∣s∣) 的空间。🌻Java 方法二：在原字符串上直接双指针判断
思路解析 直接在原字符串 s 上使用双指针。
在移动任意一个指针时，需要不断地向另一指针的方向移动，直到遇到一个字母或数字字符，或者两指针重合为止。
也就是说，我们每次将指针移到下一个字母字符或数字字符，再判断这两个指针指向的字符是否相同。
代码：
class Solution {
public boolean isPalindrome(String s) {
int n = s.length();
int left = 0, right = n - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
++left;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
--right;
}
if (left < right) {
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
++left;
--right;
}
}
return true;
}
}执行结果
通过
执行用时：2 ms，在所有 Java 提交中击败了98.39%的用户
内存消耗：38.7 MB，在所有 Java 提交中击败了21.96%的用户复杂度分析
时间复杂度：O( n )
空间复杂度：O( 1 )💬总结
- 今天是力扣算法题打卡的第三十六天！
- 文章采用
C#和Java两种编程语言进行解题 - 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
- 那今天的算法题分享到此结束啦，明天再见！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-09-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
