双指针判断回文字符串：求解《125. 验证回文串》《018. 有效的回文》《680. 验证回文字符串 Ⅱ》和《019. 最多删除一个字符得到回文》

使用双指针判断回文字符串，求解《125. 验证回文串》《剑指 Offer II 018. 有效的回文》《680. 验证回文字符串 Ⅱ》和《剑指 Offer II 019. 最多删除一个字符得到回文》

回文字符串 （Pallindrome）

• 正读或反读都相同的字符串，即回文字符串

双指针判断回文字符串

• 左指针从字符串头部，右指针从字符串尾部
  • 左右指针所指字符相同，左指针 +1，右指针 -1
  • 左右指针所指字符不同，则不是回文字符串

例题

125. 验证回文串

剑指 Offer II 018. 有效的回文

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。

答案

双指针 · 过滤 ASCII

• 0 的 ASCII 码是 45
• 9 的 ASCII 码是 57

var isPalindrome = function(s) {
  let l = 0, r = s.length - 1
  while (l < r) {
    while (l < r && isASCII(s.charCodeAt(l)) === false) l++
    while (l < r && isASCII(s.charCodeAt(r)) === false) r--
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false
    l++
    r--
  }
  return true
};
const isASCII = code => code >= 97 && code <= 122 || code >= 65 && code <= 90 || code >= 48 && code <= 57

func isPalindrome(s string) bool {
  s = strings.ToLower(s)
  l, r := 0, len(s) - 1
  for l < r {
    for l < r && isACCII(s[l]) == false {
      l++
    }
    for l < r && isACCII(s[r]) == false {
      r--
    }
    if s[l] != s[r] {
      return false
    }
    l++
    r--
  }
  return true
}
func isACCII(ch byte) bool {
  return ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '9'
}

双指针 · 正则

• 正则：过滤非 a-zA-Z0-9_ 和 _

var isPalindrome = function(s) {
  s = s.replace(/[\W|_]/g, '')
  let l = 0, r = s.length - 1
  while (l < r) {
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false
    l++
    r--
  }
  return true
};

import "regexp"
func isPalindrome(s string) bool {
  pattern := `[\W|_]`
  reg, _ := regexp.Compile(pattern)
  str := reg.ReplaceAllString(s, "")
  str = strings.ToLower(str)
  l, r := 0, len(str) - 1
  for l < r {
    if str[l] != str[r] {
      return false
    } 
    l++
    r--
  }
  return true
}

680. 验证回文字符串 Ⅱ

剑指 Offer II 019. 最多删除一个字符得到回文

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

答案

贪心·迭代

两指针有一个不同，必须有一个被删除

• 删左指针对应字符
• 删右指针对应字符

var validPalindrome = function(s) {
  let l = 0, r = s.length - 1
  while (l < r) {
    if (s[l] === s[r]) {
      l++
      r--
    } else {
      let flag1 = true, flag2 = true
      for (let i = l, j = r - 1; i < j; i++, j--) {
        if (s[i] !== s[j]) {
          flag1 = false
          break
        }
      }
      for (let i = l + 1, j = r; i < j; i++, j--) {
        if (s[i] !== s[j]) {
          flag2 = false
          break
        }
      }
      return flag1 || flag2
    }
  }
  return true
};

func validPalindrome(s string) bool {
  l, r := 0, len(s) - 1
  for l < r {
    if s[l] == s[r] {
      l++
      r--
    } else {
      flag1, flag2 := true, true
      for i, j := l, r - 1; i < j; i, j = i + 1, j - 1 {
        if s[i] != s[j] {
          flag1 = false
          break
        }
      }
      for i, j := l + 1, r; i < j; i, j = i + 1, j - 1 {
        if s[i] != s[j] {
          flag2 = false
          break
        }
      }
      return flag1 || flag2
    }
  }
  return true
}

递归

var validPalindrome = function(s) {
  let l = 0, r = s.length - 1
  while (l < r) {
    if (s[l] !== s[r]) return checkVaildPalindrome(s, l, r - 1) || checkVaildPalindrome(s, l + 1, r)
    l++
    r--
  }
  return true
};

function checkVaildPalindrome(s, l, r) {
  while (l < r) {
    if (s[l] !== s[r]) return false
    l++
    r--
  }
  return true
}

func validPalindrome(s string) bool {
  l, r := 0, len(s) - 1
  for l < r {
    if s[l] != s[r] {
      return checkValidPalindrome(s, l, r - 1) || checkValidPalindrome(s, l + 1, r)
    }
    l++
    r--
  }
  return true
}

func checkValidPalindrome(s string, l int, r int) bool {
  for l < r {
    if s[l] != s[r] {
      return false
    }
    l++
    r--
  }
  return true
}