首页 > 代码库 > leetcode:Valid Palindrome
leetcode:Valid Palindrome
一、 题目
题目给出一个字符串,求出它是否为回文字符串,其中只有字母和数字是有效字符,其他的字符可以忽略。
例如:"Aman, a plan, a canal: Panama" 是回文字符串.
"race a car" is not a palindrome.不是回文字符串
二、 分析
看到这个题目我首先想到的是使用两个数组将有效字符串保存,其中一个正序一个逆序,然后做比较。但是考虑到效率和空间使用,可以使用“两指针法”,即设置一个左指针一个右指针,相向移动,判断他们的有效值是否相等,不相等则直接false,直到相遇。
class Solution { public: //判断字符是不是字母或字符 bool isAlphanumeric(char c) { if((c >= 'a' && c <= 'z')||(c >= 'A' && c <= 'Z')||(c >= '0' && c <= '9')) return true; else return false; } bool isPalindrome(string s) { int len = s.size(); //判断是否为空,为空则返回真 if(len == 0) return true; int left=0; int right = len-1; while(left<right){ //注意判断left是否小于len,当时就卡在这了 if(!isAlphanumeric(s[left])&&left<=len-1){ left++; } else if(!isAlphanumeric(s[right])&&right>=0){ right--; } else { //注意字母的大小写,这里只需要判断字母是否相等或差的绝对值是否为32 if(s[left] != s[right]&&fabs(s[left]-s[right])!=32) return false; left++; right--; } } return true; } };
leetcode:Valid Palindrome
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。