目录
1.题目
https://leetcode.cn/problems/XltzEq/description/
给定一个字符串
s，验证s是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。本题中，将空字符串定义为有效的 回文串 。
示例 1:
输入: s = "A man, a plan, a canal: Panama" 输出: true 解释："amanaplanacanalpanama" 是回文串示例 2:
输入: s = "race a car" 输出: false 解释："raceacar" 不是回文串
提示：
1 <= s.length <= 2 * 105- 字符串
s由 ASCII 字符组成
2.自解
将原数组中所有字母(将小写字母转换为大写字母)和数字字符复制到另一个数组中之后用双指针算法
双指针算法参见L8.【LeetCode笔记】回文数
bool isPalindrome(char * s)
{
if (s==NULL)
return true;
int length=strlen(s);
char* arr=(char*)malloc(length);
int length_c=0;
for (int i=0;i<length;i++)
{
if (!((s[i]>='A'&&s[i]<='Z')||(s[i]>='a'&&s[i]<='z')||(s[i]>='0' &&s[i]<='9')))
continue;
arr[length_c++]=toupper(s[i]);
}
char* left=&arr[0];
char* right=&arr[length_c-1];
while (left < right)
{
if (*left == *right)
{
left++;
right--;
continue;
}
else
return false;
}
free(arr);
return true;
}备注:toupper函数为将小写字母转换为大写字母返回,如果非小写字母,返回原字符
cplusplus网对该函数的详细解释
提交结果
空间复杂度为,可以想办法降至
反思
其实没有必要调用toupper,用位运算更加简洁而且更快
'A': 0100 0001b 'a': 0110 0001b 'Z': 0101 1010 'z': 0111 1010 ,可以发现大小写之间只差了
0010_ 0000b
大小写之间的位运算
对于字符c有
c ^ 32 大小写反转 (汇编 xor byte c,0010_0001b)
c | 32 大写转小写或者小写转小写(汇编 or byte c,0010_0001b)
c & ~32 小写转大写或者大写转大写(汇编 and byte c,1101_1111b)
因此将arr[length_c++]=toupper(s[i]);改成arr[length_c++]=s[i] & ~32;或arr[length_c++]=s[i] | 32;都可
提交结果
3.代码优化
直接在原数组的基础上使用双指针,时间复杂度为
bool isPalindrome(char * s)
{
if (s==NULL)
return true;
int length=strlen(s);
char* left=&s[0];
char* right=&s[length-1];
while (left < right)
{
if (!((*left>='A'&&*left<='Z')||(*left>='a'&&*left<='z')||(*left>='0' &&*left<='9')))
{
left++;
continue;
}
if (!((*right>='A'&&*right<='Z')||(*right>='a'&&*right<='z')||(*right>='0' &&*right<='9')))
{
right--;
continue;
}
if ((*left| 32) == (*right| 32))
{
left++;
right--;
continue;
}
else
return false;
}
return true;
}
注意这里:*left和*right强制转为小写再比较(*left| 32) == (*right| 32)
提交结果
4.LeetCode网友提供的解法
bool isPalindrome(char* s)
{
int len = strlen(s);
int i = 0, j = 0;
for (i = 0, j = len - 1; i < j; i++, j--)
{
for (; !isdigit(s[i]) && !isalpha(s[i]) && i < j;)
{
i++;
}
for (; !isdigit(s[j]) && !isalpha(s[j]) && i < j;)
{
j--;
}
s[i] = toupper(s[i]);
s[j] = toupper(s[j]);
if (s[i] != s[j])
{
return false;
}
}
return true;
}积累两个函数
isdigit(c):如果待检测的字符c是0到9之间(十进制)的数字字符,则返回非0值,否则返回0
isalpha(c):如果待检测的字符c字母,则返回非0值,否则返回0