当前位置：首页 > news >正文

L23.【LeetCode笔记】验证回文串(剖析几种解法)

news 2024/12/14 17:55:41

1.题目

2.自解

提交结果

反思

大小写之间的位运算

提交结果

3.代码优化

提交结果

编辑

4.LeetCode网友提供的解法

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;}elsereturn false;}free(arr);return true;}

备注:toupper函数为将小写字母转换为大写字母返回,如果非小写字母,返回原字符

cplusplus网对该函数的详细解释

提交结果

空间复杂度为 $eq?O%28N%29$ ,可以想办法降至 $eq?O%281%29$

反思

其实没有必要调用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.代码优化

直接在原数组的基础上使用双指针,时间复杂度为 $eq?O%281%29$

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;}elsereturn 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;
}

积累两个函数