leetcode-125-Valid Palindrome

MATLAB 2018-05-29

题目描述:

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note:For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

要完成的函数:

bool isPalindrome(string s)

说明:

1、给定一个字符串s,要求判断这个字符串是不是回文串。这道题跟普通题目不一样的地方在于,字符串中可能会有非字母和非数字,比如空格符和标点符号,我们需要过滤掉它们。

也有可能会有大小写字母,也需要大写转换为小写。

2、明白题意,我们构造代码如下:(附详解)

bool isPalindrome(string s) 
    {
        int i=0,s1=s.size(),j=s1-1;
        while(i<j)
        {
            while(!isalnum(s[i])&&i<=j)//一直找,直到找到字母或者数字,并且不能超过j
                i++;
            if(i==j+1)//如果超过j了,到达j+1,说明从初始的i到j的中间区域都没有字母或者数字,这时候返回true。比如[,.]这样的例子。
                return true;
            while(!isalnum(s[j]))//一直找,直到找到字母或者数字。这里不加i<=j这个判断条件是因为,前面在中间区域找得到,那么这里也必定找得到
                j--;
            if(tolower(s[i])==tolower(s[j]))//要转换大小写
            {
                i++;
                j--;
            }
            else
                return false;
        }
        return true;
    }

上述代码实测10ms,beats 95.16% of cpp submissions。

相关推荐

北美码农的包子铺 / 0评论 2018-01-28
软件设计 / 0评论 2017-03-29