C++实现LeetCode(125.验证回文字符串)

[LeetCode] 125.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++实现LeetCode(验证回文字符串)的文章就介绍到这了,更多相关C++验证回文字符串内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • c语言描述回文数的三种算法

    题目描述 注意:(这些回文数都没有前导0) 1位的回文数有0,1,2,3,4,5,6,7,8,9 共10个: 2位的回文数有11,22,33,44,55,66,77,88,99 共9个: * 请问:n位的回文数有多少个?请编写一个递归函数来解决此问题!!! [输入形式]一行一个正整数,代表多少位 [输出形式]一行一个正整数,代表回文诗的个数 [样例输入]2 [样例输出]9 输入: 3 输出: 90 输入: 5 输出: 900 **输入: 10 输出: 90000** 输入: 8 输出: 9000

  • C语言用栈和队列实现的回文检测功能示例

    C语言用栈和队列实现的回文检测功能示例

    本文实例讲述了C语言用栈和队列实现的回文功能.分享给大家供大家参考,具体如下: #include<stdio.h> #include<malloc.h>//内存分配头文件 #include<math.h>//在math.h中已定义OVERFLOW的值为3 #define SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typede

  • C语言算法打卡回文串验证算法题解

    C语言算法打卡回文串验证算法题解

    目录 概念 Leetcode例题: 1.回文串的验证 2.有效回文 3.回文排列 点杀回文排列 点杀回文验证(有效性) 对撞指针 概念 所谓回文串,就是字符串反转以后和原串相同,如 abba 和 lippil.对于回文串还是比较容易去验证的,从字符数组的两端开始向中间靠拢去验证字符是否相等,但这里是否需要考虑字符数组长度的奇偶性呢?其实是不用的,下面一起来看看: Leetcode例题: 1.回文串的验证 2.有效回文 3.回文排列 (1,2题是一样的,合并讲解吧) 点杀回文排列 先讲回文排列吧,

  • C语言如何用顺序栈实现回文序列判断

    C语言如何用顺序栈实现回文序列判断

    我是采用了两个栈值得比较大小判断得(可能比较浪费空间但是代码我感觉简单一点) 首先是定义一个栈的结构元素,由于是字符串类型就直接定义一个char的数组就可以:. typedef struct stack { char data[MAX_SIZE]; //储存字符串// int top; //记录栈顶// }SeqStack; 下来就是初始化,我这里是用的耿国华老师的方法就直接给一个top元素指向栈顶,传入的指针地址:. void Initstack(SeqStack *S) //初始化栈,让to

  • C++/C 回文字符串的实例详解

    C++/C 回文字符串的实例详解

    C++/C回文字符串的实例详解 判断输入的字符串是不是回文字符串,正反读一样. .C版 #include<stdio.h> int main() { char he[100]; char a; int i=0,flag=1; while((a=getchar())!='\n') { he[i]=a; i++; } int n=i; for(i=0;i<n/2;i++) { printf("%c\t%c\n",he[i],he[n-1-i]); if(he[i]!=he

  • C++实现LeetCode(125.验证回文字符串)

    [LeetCode] 125.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

  • C++实现LeetCode(验证回文字符串)

    [LeetCode] 125.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

  • C++实现LeetCode(9.验证回文数字)

    [LeetCode] 9. Palindrome Number 验证回文数字 Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward. Example 1: Input: 121 Output: true Example 2: Input: -121 Output: false Explanation: From left

  • Python实现"验证回文串"的几种方法

    一.LeetCode--125.验证回文串 1.问题描述 给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写. 说明:本题中,我们将空字符串定义为有效的回文串. 2.示例 示例 1: 输入: "A man, a plan, a canal: Panama" 输出: True 示例 1: 输入: "race a car" 输出: False 示例 3: 输入: "!!!" 输出: True 二.解题分析 在排除空格及特殊

  • C++实现LeetCode(132.拆分回文串之二)

    [LeetCode] 132.Palindrome Partitioning II 拆分回文串之二 Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. Example: Input: "aab" Output: 1 Explan

  • C++实现LeetCode(131.拆分回文串)

    [LeetCode] 131.Palindrome Partitioning 拆分回文串 Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Example: Input: "aab" Output: [ ["aa","b"

  • PHP判断一个字符串是否是回文字符串的方法

    本文实例讲述了PHP判断一个字符串是否是回文字符串的方法.分享给大家供大家参考.具体实现方法如下: <?php function ishuiwen($str){ $len=strlen($str); $l=1; $k=intval($len/2)+1; for($j=0;$j<$k;$j++){ if (substr($str,$j,1)!=substr($str,$len-$j-1,1)) { $l=0; break; } } if ($l==1) { return 1; } else {

  • Python回文字符串及回文数字判定功能示例

    本文实例讲述了Python回文字符串及回文数字判定功能.分享给大家供大家参考,具体如下: 所谓回文字符串,就是一个字符串,从左到右读和从右到左读是完全一样的.回文数字也是如此. python2代码如下: def huiwen(s): s1=str(s) if s1==''.join(reversed(s1)): return True else: return False 运行结果: >>> huiwen('abccba') True >>> huiwen('abc')

  • Python实现常见的回文字符串算法

    回文 利用python 自带的翻转 函数 reversed() def is_plalindrome(string): return string == ''.join(list(reversed(string)))` 自己实现 def is_plalindrome(string): string = list(string) length = len(string) left = 0 right = length - 1 while left < right: if string[left]

随机推荐