C++怎么实现验证回文字符串
这篇文章主要讲解了“C++怎么实现验证回文字符串”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C++怎么实现验证回文字符串”吧!
成都创新互联是一家网站设计公司,集创意、互联网应用、软件技术为一体的创意网站建设服务商,主营产品:响应式网站建设、品牌网站建设、全网整合营销推广。我们专注企业品牌在网站中的整体树立,网络互动的体验,以及在手机等移动端的优质呈现。成都做网站、网站设计、移动互联产品、网络运营、VI设计、云产品.运维为核心业务。为用户提供一站式解决方案,我们深知市场的竞争激烈,认真对待每位客户,为客户提供赏析悦目的作品,网站的价值服务。
Valid Palindrome 验证回文字符串
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
验证回文字符串是比较常见的问题,所谓回文,就是一个正读和反读都一样的字符串,比如“level”或者“noon”等等就是回文串。但是这里,加入了空格和非字母数字的字符,增加了些难度,但其实原理还是很简单:只需要建立两个指针,left和right, 分别从字符的开头和结尾处开始遍历整个字符串,如果遇到非字母数字的字符就跳过,继续往下找,直到找到下一个字母数字或者结束遍历,如果遇到大写字母,就将其转为小写。等左右指针都找到字母数字时,比较这两个字符,若相等,则继续比较下面两个分别找到的字母数字,若不相等,直接返回false.
时间复杂度为O(n), 代码如下:
解法一:
class Solution { public: bool isPalindrome(string s) { int left = 0, right = s.size() - 1 ; while (left < right) { if (!isAlphaNum(s[left])) ++left; else if (!isAlphaNum(s[right])) --right; else if ((s[left] + 32 - "a") %32 != (s[right] + 32 - "a") % 32) return false; else { ++left; --right; } } return true; } bool isAlphaNum(char &ch) { if (ch >= "a" && ch <= "z") return true; if (ch >= "A" && ch <= "Z") return true; if (ch >= "0" && ch <= "9") return true; return false; } };
我们也可以用系统自带的判断是否是数母字符的判断函数isalnum,参见代码如下;
解法二:
class Solution { public: bool isPalindrome(string s) { int left = 0, right = s.size() - 1 ; while (left < right) { if (!isalnum(s[left])) ++left; else if (!isalnum(s[right])) --right; else if ((s[left] + 32 - "a") %32 != (s[right] + 32 - "a") % 32) return false; else { ++left; --right; } } return true; } };
感谢各位的阅读,以上就是“C++怎么实现验证回文字符串”的内容了,经过本文的学习后,相信大家对C++怎么实现验证回文字符串这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是创新互联,小编将为大家推送更多相关知识点的文章,欢迎关注!
网站栏目:C++怎么实现验证回文字符串
转载源于:http://myzitong.com/article/gisjsp.html