LeetCode Problem: Valid Palindrome

By | 2013 年 1 月 19 日

To solving this problem, using two pointer to track the characters in the string. i, from the beginning of string; j, from the back of the string.
这个问题简单,只需要收尾两个指针相向而行,比较是否相等就可以了,过程中跳过不是字母也不是数字的字符。算法如下:

while i < j do {
  1.if s[i] is not alphanumeric, moving i forward and continue
  2.if s[j] is not alphanumeric, moving j backward and condinue
  3.if s[i] != s[j] (ignoring the cases) return false.
  4.moving i forward and j backward by one step
}
return true;



Valid Palindrome Jan 13
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.



Code, 60ms pass large set

class Solution {
    inline bool isAlpha(char c) {
        if(c >= 'a' && c <= 'z') return true;
        if(c >= 'A' && c <= 'Z') return true;
        if(c >= '0' && c <= '9') return true;
        return false;
    }
    inline char lower(char c) {
        if(c >= 'A' && c <= 'Z')
            return ('a' + (c-'A'));
        return c;
    }
public:
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i = 0, j = s.size() - 1;
        while(i < j) {
            if(!isAlpha(s[i])) {
                ++i;
                continue;
            }
            if(!isAlpha(s[j])) {
                --j;
                continue;
            }
            if(lower(s[i++]) != lower(s[j--])) {
                return false;
            }
        }
        return true;
    }
};



Code rewrite at 2013-2-4

class Solution {
    bool isValidChar(char c) {
        if (c >= '0' && c <= '9')
            return true;
        if (c >= 'a' && c <= 'z')
            return true;
        if (c >= 'A' && c <= 'Z') {
            return true;
        }
        return false;
    }
    char lower(char c) {
        if (c >= 'A' && c <= 'Z') {
            return 'a' + c - 'A';
        }
    }
public:
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(s.size() <= 1) return true;
        int si=0,ei=s.size()-1;
        while(si < ei) {
            while(si < ei && !isValidChar(s[si]))
                ++si;
            while(si < ei && !isValidChar(s[ei]))
                --ei;
            if(lower(s[si]) != lower(s[ei])) {
                return false;
            }
            ++si;--ei;
        }
        return true;
    }
};



Code rewrite at 2013-03-03

class Solution {
    bool isValid(char c) {
        if (c >= '0' && c <= '9')
            return true;
        if (c >= 'a' && c <= 'z')
            return true;
        if (c >= 'A' && c <= 'Z') {
            return true;
        }
        return false;
    }
    char lower(char c) {
        if (c >= 'A' && c <= 'Z') {
            return 'a' + c - 'A';
        }
    }
public:
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(s.size() <= 1) return true;
        int si=0,ei=s.size()-1;
        while(si < ei) {
            if(!isValid(s[si])) {
                ++si;
                continue;
            }
            if(!isValid(s[ei])) {
                --ei;
                continue;
            }
            if(lower(s[si++]) != lower(s[ei--])) {
                return false;
            }
        }
        return true;
    }
};

3 thoughts on “LeetCode Problem: Valid Palindrome

  1. zhangyuxiu

    我认为第二种算法,isPalindrome函数的大while循环应该为:
    while(si < ei) {
    while(si < ei && !isValidChar(s[si]))
    ++si;
    while(si < ei && !isValidChar(s[ei]))
    –ei;
    if (si == ei ) return true; //当s[si]为非字符数字时,其没有lower()值。
    if(lower(s[si]) != lower(s[ei])) {
    return false;
    }
    ++si;–ei;
    }

    Reply
    1. uniEagle Post author

      刚才重写了一个,while里面还是用continue来处理比较好,不用写循环嵌套,那样会多几个si

      Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注