125. Valid Palindrome - LeetCode

125. Valid Palindrome

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

Solution1:

过滤成回文串去计算, 需要O(n)的空间复杂度

// Time:O(n), Space:O(n)
class Solution {
 public:
  bool isPalindrome(string s) {
    if (s.length() == 0) return true;
    string t;
    for (char c : s) {
      if (isdigit(c) || isalpha(c)) {
        t += tolower(c);
      }
    }
    int n = t.length();
    for (int i = 0; i <= n/2; i++) {
      if (t[i] != t[n-1-i]) return false;
    }
    return true;
  }
};

Solution2:

用two pointers的方法, 在原地进行判断,

注意点:

• 数字和字母, 可以用isalnum()这个函数..
• 注意还要ignore case, 因此使用tolower在判断前。

// Time:O(n), Space:O(1)
// two pointers, in-place
class Solution {
 public:
  bool  isPalindrome(string s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
      while (isalnum(s[i]) == false && i < j) i++;
      while (isalnum(s[j]) == false && i < j) j--;
      if (tolower(s[i]) != tolower(s[j])) return false;
      i++;
      j--;
    }
    return true;
  }
};