题意：

解题思路：

  1. 思路：
  2. (线性扫描) O(n)
  3. 1. 用两个指针分别从前后开始，往中间扫描。
  4. 2. 每次迭代两个指针分别向中间靠近一步，靠近的过程中忽略除了字母和数字的其他字符。
  5. 3. 然后判断两个指针所指的字符是否相等，如果不相等，说明不是回文串。
  6. 4.当两个指针相遇时，说明原字符串是回文串。
  8. 时间复杂度分析：每个字符仅会被扫描一次，所以时间复杂度是 O(n)。

PHP代码实现：

  1. class Solution {
  2.     function isAlphanumeric($s) {
  3.         return ($s >= 'a' && $s <= 'z') || ($s >= 'A' && $s <= 'Z')
  4.             || ($s >= '0' && $s <= '9');
  5.     }
  7.     function isEqualIgnoreCase($a, $b) {
  8.         if ($a >= 'A' && $a <= 'Z') $a = strtolower($a);
  9.         if ($b >= 'A' && $b <= 'Z') $b = strtolower($b);
  10.         return $a == $b;
  11.     }
  13.     function isPalindrome1($s) {
  14.         if ($s == null || strlen($s) == 0) return true;
  15.         $i = 0; $j = strlen($s) - 1;
  17.         for (; $i < $j; ++$i, --$j) {
  18.             //不是字母或者数字，i < j:防止移动到j后面
  19.             while ($i < $j && !$this->isAlphanumeric($s[$i])) ++$i; 
  20.             while ($i < $j && !$this->isAlphanumeric($s[$j])) --$j; 
  21.             if ($i < $j && strtolower($s[$i]) != strtolower($s[$j])) return false;
  22.         }
  23.         return true;
  24.     }
  25.     /**
  26.      * @param String $s
  27.      * @return Boolean
  28.      */
  29.     function isPalindrome($s) {
  30.         return $this->isPalindrome1($s);
  31.         if (empty($s)) return true;
  32.         $str = $rStr = '';
  33.         $count = strlen($s);
  34.         $l = 0;
  35.         $r = $count - 1;
  37.         while ($l < $r) {
  38.             $lLetter = $this->isLetter($s[$l]);
  39.             $rLetter = $this->isLetter($s[$r]);
  40.             if ($lLetter === false) {
  41.                 $l++;
  42.                 continue;
  43.             }
  44.             if ($rLetter === false) {
  45.                 $r--;
  46.                 continue;
  47.             }
  48.             if ($lLetter != $rLetter) {
  49.                 return false;
  50.             }
  51.             $l++;$r--;
  52.         }
  53.         return true;
  54.     }
  56.     function isLetter($str) {
  57.         if ($str >= 'a' && $str <= 'z') {
  58.             return $str;
  59.         } else if ($str >= 'A' && $str <= 'Z') {
  60.             return chr(ord($str) + 32);
  61.         } else if (in_array($str,['0','1','2','3','4','5','6','7','8','9'])) {
  62.             return $str;
  63.         }
  64.         return false;
  65.     }
  66. }

GO代码实现：

  1. func isPalindrome(s string) bool {
  2.     if s == "" {
  3.         return true
  4.     }
  5.     s = strings.ToLower(s)
  6.     n := len(s)
  7.     i, j := 0, n-1
  8.     for i < j {
  9.         if !isValidChar(s[i]) {
  10.             i++
  11.             continue
  12.         }
  13.         if !isValidChar(s[j]) {
  14.             j--
  15.             continue
  16.         }
  17.         if s[i] != s[j] {
  18.             return false
  19.         }
  20.         i++
  21.         j--
  22.     }
  23.     return true
  24. }
  26. func isValidChar(char byte) bool {
  27.     return (char >= 'A' && char <= 'Z') || 
  28.         (char >= 'a' && char <= 'z') || 
  29.         (char >= '0' && char <= '9')
  30. }