验证回文串
# 📃 题目描述
题目链接:
- 剑指 Offer II 018. 有效的回文 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 125. 验证回文串 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个字符串 s ,验证 s 是否是 回文串 ,只考虑字母和数字字符,可以忽略字母的大小写。
本题中,将空字符串定义为有效的 回文串。
示例 1:
输入: s = "A man, a plan, a canal: Panama"
输出: true
解释:"amanaplanacanalpanama" 是回文串
# 🔔 解题思路
比较简单,判断一个字符串是不是回文,常用的方法就是使用双指针。可以定义两个指针,一个指针从第 1 个字符开始从前向后移动,另一个指针从最后一个字符开始从后向前移动。如果两个指针指向的字符相同,则同时移动这两个指针以判断它们指向的下一个字符是否相同。这样一直移动下去,直到两个指针相遇。
由于两个指针移动的总次数最多等于字符串的长度,因此该解法的时间复杂度是 O(N)
class Solution {
public boolean isPalindrome(String s) {
if (s == null || s.length() <= 1) {
return true;
}
int left = 0;
int right = s.length() - 1;
while (left < right) {
char ch1 = s.charAt(left);
char ch2 = s.charAt(right);
if (!Character.isLetterOrDigit(ch1)) {
left ++;
continue;
}
if (!Character.isLetterOrDigit(ch2)) {
right --;
continue;
}
ch1 = Character.toLowerCase(ch1);
ch2 = Character.toLowerCase(ch2);
if (ch1 != ch2) {
return false;
}
else {
left ++;
right --;
}
}
return true;
}
}
# 💥 复杂度分析
- 空间复杂度:O(1)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10