125-验证回文串
访问量:786

一、简介

地址:https://leetcode.com/problems/valid-palindrome/

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

说明:本题中,我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"

输出: true


示例 2:

输入: "race a car"

输出: false


二、解法

1、解法1

思路:第一个字母或数字,跟倒数第一个字母或数字比较,第二个字母或数字,跟倒数第二个字母或数字比较,一直比较到中间的位置。不相等,则返回false。由于只考虑字母和数字字符,所以,比较的时候,要么我们先把所有非字母和数字字符删除掉,要么在比较的时候,注意忽略非字母和数字字符。考虑到,删除非字母字母和数字字符会降低效率,所以我们采用忽略的方式。实现如下:

func isPalindrome(s string) bool {
   var rightIndex int = len(s) - 1
   var leftIndex int = 0

   for leftIndex < rightIndex {
      //取left需要比较的字符
      if s[leftIndex] < 48 || s[leftIndex] > 122 || s[leftIndex] > 57 && s[leftIndex] < 65 || s[leftIndex] > 90 && s[leftIndex] < 97 {
         leftIndex ++
         continue
      }

      //判断 是否为字母或是数字
      if s[rightIndex] < 48 || s[rightIndex] > 122 || s[rightIndex] > 57 && s[rightIndex] < 65 || s[rightIndex] > 90 && s[rightIndex] < 97 {
         rightIndex --
         continue
      }

      if s[rightIndex] != s[leftIndex] {
         if s[rightIndex] < 65 || s[leftIndex] < 65 {
            return false
         }
         var tmp byte
         if s[rightIndex] > s[leftIndex] {
            tmp = s[rightIndex] - s[leftIndex]
         } else {
            tmp = s[leftIndex] - s[rightIndex]
         }

         if tmp != 32 {
            return false
         }
      }
      leftIndex ++
      rightIndex --
   }

   return true
}