首页 > 代码库 > 【LeetCode】Valid Palindrome

【LeetCode】Valid Palindrome

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.

 

左右分别往中间扫描,如果不同则返回false,如果两端碰面了则返回true

代码里写了很多注释,我认为这类题难点在于循环的判断条件以及跳出条件

因此对于每一个循环都需要明确它的进入条件以及跳出条件。

class Solution {public:    bool isPalindrome(string s) {        if(s.empty())            return true;        else        {            int left = 0;            int right = s.size()-1;            //initilize c1 == c2, in case no move for left or right            char c1 = \0;            char c2 = \0;            while(left < right)            {//when left >= right, means true when left < right, jump out                while(left < right)                {                    if(s[left] >= a && s[left] <= z)                    {//lowercase                        c1 = s[left];                        break;                    }                    else if(s[left] >= A && s[left] <= Z)                    {//capital                        c1 = tolower(s[left]);                        break;                    }                    else if(s[left] >= 0 && s[left] <= 9)                    {//number                        c1 = tolower(s[left]);                        break;                    }                    else                    // not a letter                        left ++;                }                //when come here, either left==right(1) or find next c1(2)                //case (1): c1 and c2 remain unchanged and break out of while and return true                //case (2): c1 get a new char                if(left == right)                //case (1)                    return true;                //case (2)                while(left <= right)                {//careful! c2 must update the value as c1, even if the same position                    if(s[right] >= a && s[right] <= z)                    {//lowercase                        c2 = s[right];                        break;                    }                    else if(s[right] >= A && s[right] <= Z)                    {//capital                        c2 = tolower(s[right]);                        break;                    }                    else if(s[right] >= 0 && s[right] <= 9)                    {//number                        c2 = tolower(s[right]);                        break;                    }                    else                    // not a letter                        right --;                }                                //If come here, that means c1 and c2 are both updated                if(c1 != c2)                    return false;                else                {                    left ++;                    right --;                }            }            return true;        }    }};

【LeetCode】Valid Palindrome