1. 题目描述
题目链接:125. 验证回文串
2. 解题思路
这道题不难,分为两种情况:
(1)如果是空串,直接返回 ture
(2)新开一个 string 对象 s2,把 s 字符串里面的字符存进 s2(先将原本字符的特殊字符去掉,如果遇到大写字符就转换为小写字符)
(3)然后用两个指针,一个指向起始位置,另一个指向最后一个元素位置,从两边开始向中间遍历,判断是否相等。
3. 代码实现
空间复杂度
O
(
n
)
O(n)
O(n)
class Solution {
public:
bool isPalindrome(string s) {
//空串
if (s == " ") {
return true;
}
//不是空串
string s2;
for (int i = 0; i < s.size(); ++i) {
if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
if ((s[i] >= 'a' && s[i] <= 'z')) {
s2 += s[i];
}
else {
s2 += (s[i] + 32);
}
}
}
int i = 0;
int j = s2.size() - 1;
for (i = 0, j = s2.size() - 1; i <= j; ++i, --j) {
if (s2[i] == s2[j]) {
continue;
}
else {
return false;
}
}
return true;
}
};
还可以不开空间
class Solution {
public:
bool isLetterOrNumber(char ch) {
return (ch >= '0' && ch <= '9')
|| (ch >= 'a' && ch <= 'z')
|| (ch >= 'A' && ch <= 'Z');
}
bool isPalindrome(string s) {
// 先小写字母转换成大写,再进行判断
for (auto& ch : s) {
if (ch >= 'a' && ch <= 'z')
ch -= 32;
}
int begin = 0, end = s.size() - 1;
while (begin < end)
{
while (begin < end && !isLetterOrNumber(s[begin]))
++begin;
while (begin < end && !isLetterOrNumber(s[end]))
--end;
if (s[begin] != s[end])
{
return false;
}
else
{
++begin;
--end;
}
}
return true;
}
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/80842.html