题目

给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

示例 1:输入: s = "aba" 输出: true

示例 2:输入: s = "abca" 输出: true

解释: 可以删除 "c" 字符 或者 "b" 字符

示例 3:输入: s = "abc" 输出: false

提示:1 <= s.length <= 105

s 由小写英文字母组成

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

解题思路分析

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

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

func isPalindrome(s string, i, j int) bool {
   for i < j {
      if s[i] != s[j] {
         return false
      }
      i++
      j--
   }
   return true
}

2、递归；时间复杂度O(n)，空间复杂度O(n)

func validPalindrome(s string) bool {
   length := len(s)
   if length < 2 {
      return true
   }
   if s[0] == s[length-1] {
      return validPalindrome(s[1 : length-1])
   }
   return isPalindrome(s[0:length-1]) || isPalindrome(s[1:length])
}

func isPalindrome(s string) bool {
   i := 0
   j := len(s) - 1
   for i < j {
      if s[i] != s[j] {
         return false
      }
      i++
      j--
   }
   return true
}

总结

Easy题目，题目同leetcode 680.验证回文字符串 Ⅱ