题目

给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。

本题中，将空字符串定义为有效的 回文串 。

示例 1:输入: s = "A man, a plan, a canal: Panama" 输出: true

解释："amanaplanacanalpanama" 是回文串

示例 2:输入: s = "race a car" 输出: false

解释："raceacar" 不是回文串

提示：1 <= s.length <= 2 * 105

字符串 s 由 ASCII 字符组成

注意：本题与主站 125 题相同

解题思路分析

1、双指针；时间复杂度O(n)，空间复杂度O(1)

func isPalindrome(s string) bool {
   s = strings.ToLower(s)
   i, j := 0, len(s)-1

   for i < j {
      for i < j && !isChar(s[i]) {
         i++
      }
      for i < j && !isChar(s[j]) {
         j--
      }
      if s[i] != s[j] {
         return false
      }
      i++
      j--
   }
   return true
}

func isChar(c byte) bool {
   if ('a' <= c && c <= 'z') || ('0' <= c && c <= '9') {
      return true
   }
   return false
}

2、双指针；时间复杂度O(n)，空间复杂度O(n)

func isPalindrome(s string) bool {
   str := ""
   s = strings.ToLower(s)
   for _, value := range s {
      if (value >= '0' && value <= '9') || (value >= 'a' && value <= 'z') {
         str += string(value)
      }
   }
   if len(str) == 0 {
      return true
   }
   i := 0
   j := len(str) - 1
   for i <= j {
      if str[i] != str[j] {
         return false
      }
      i++
      j--
   }
   return true
}

总结

Easy题目，题目同leetcode 125.验证回文串