给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
解释:"amanaplanacanalpanama" 是回文串
示例 2:
输入: "race a car"
输出: false
解释:"raceacar" 不是回文串
提示:
1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成
思路如下:
这个时候我们一般定义双指针来进行比较,一个从左边开始,一个从右边开始,将所指的数组元素进行比较,直到两个指针指向同一个位置或者左边指针指向的位置大于右边指针指向的位置。
这里有几个需要注意的点:
1.字母或数字都有可能被比较。
2.字母有可能是大写,有可能是小写。
3.输入的字符里可能有特殊符号,我们得过滤掉这些符号。
char str(char ch)
{
if (ch >= 'A' && ch <= 'Z')
return ch + 32;
return ch;
}
bool isPalindrome(char * s){
int n = strlen(s);
char* arr = malloc(sizeof(char) * (n));
memset(arr, 0, sizeof(char) * (n));
int size = 0;
for (int i = 0; i < n; i++)
{
if (isalnum(s[i]))
{
s[i] = str(s[i]);
arr[size++] = s[i];
}
}
char* p = arr, * q = arr + size - 1;
for (; p <= q;)
{
if (*p != *q)
return false;
p++;
q--;
}
return true;
}