这是第二道题。

题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: “A man, a plan, a canal: Panama” 输出: true

示例 2:

输入: “race a car” 输出: false

解题思路

思路一：

从题目中可以知道只需要考虑字母和数字且不区分大小写，所以直接比较原字符串比较复杂，先转换成只包含字母和数字，且全部转换成小写字母，然后进行比较就可以了。 步骤如下：

字符串转换成小写字母和数字；比较字符串是否对称。

思路二：

直接两个索引分别从头、尾开始，分别找到第一个是字母或者数字的字符，开始比较，循环遍历到索引相遇。 这样写感觉比较复杂，但是省内存。

我用的第一种思路。

代码

bool isPalindrome(char * s) { char acTmp[1000000]; /* 这里偷懒没有或取s长度，申请内存；好吧，其实是我忘了 */ bool bRet = true; int iStrLen = 0; int iLoop = 0; int i; char cTrans = 'A' - 'a'; while (0 != *s) { if ((('a' <= *s) && (*s <= 'z')) || (('0' <= *s) && (*s <= '9'))) { acTmp[iStrLen++] = *s; } else if (('A' <= *s) && (*s <= 'Z')) { acTmp[iStrLen++] = *s - cTrans; } s++; } iLoop = iStrLen / 2; --iStrLen; for (i = 0; i < iLoop; i++) { if (acTmp[i] != acTmp[iStrLen - i]) /* 注释1 */ { bRet = false; break; } } return bRet; }

易错点： 说是易错点，其实是我出错的地方。

我忘记了数字也要判断；注释1 的地方又又又越界了。

运行结果

看答案

bool isPalindrome(char * s){ if (s == NULL) { return true; } int cnt = 0; for (int i = 0; s[i] != '\0'; i++) { if (s[i] >= 'A' && s[i] <= 'Z'){ cnt++; } else if (s[i] >= 'a' && s[i] <= 'z') { cnt++; } else if (s[i] >= '0' && s[i] <= '9') { cnt++; } } char *p = (char *)malloc(cnt*sizeof(char)); int tmp = 0; for (int i = 0; s[i] != '\0'; i++) { if (s[i] >= 'A' && s[i] <= 'Z'){ p[tmp++] = s[i] + 'a' - 'A'; } else if (s[i] >= 'a' && s[i] <= 'z') { p[tmp++] = s[i] ; } else if (s[i] >= '0' && s[i] <= '9') { p[tmp++] = s[i] ; } } for (int i = 0, j = cnt - 1; i < cnt;) { if(p[i++] != p[j--]) { return false; } } return true; }

好像也差不多。。为啥这个0ms我的8ms。。。

总结

内存越界的问题还是很容易犯的。