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 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++实现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

  • 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"

  • C++实现LeetCode(6.字型转换字符串)

    [LeetCode] 6. ZigZag Conversion 之字型转换字符串 The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P   A   H   N A P L S I I G Y  

  • 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(647.回文子字符串)

    [LeetCode] 647. Palindromic Substrings 回文子字符串 Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of sa

  • C++实现LeetCode(7.翻转整数)

    [LeetCode] 7. Reverse Integer 翻转整数 Given a 32-bit signed integer, reverse digits of an integer. Example 1: Input: 123 Output: 321 Example 2: Input: -123 Output: -321 Example 3: Input: 120 Output: 21 Note: Assume we are dealing with an environment whi

  • 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(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

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

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

  • 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

  • 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]

  • C++实现LeetCode(5.最长回文子串)

    [LeetCode] 5. Longest Palindromic Substring 最长回文子串 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Example 1: Input: "babad" Output: "bab" Note: "aba" is als

随机推荐