【LeetCode每日一题】——680.验证回文串 II

一【题目类别】

• 贪心算法

二【题目难度】

• 简单

三【题目编号】

• 680.验证回文串 II

四【题目描述】

• 给你一个字符串 s，最多 可以从中删除一个字符。
• 请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

五【题目示例】

• 示例 1：

  • 输入：s = “aba”
  • 输出：true

• 示例 2：

  • 输入：s = “abca”
  • 输出：true
  • 解释：你可以删除字符 ‘c’ 。

• 示例 3：

  • 输入：s = “abc”
  • 输出：false

六【解题思路】

• 利用贪心算法的思想，由外到内逐层判断是否是回文串
• 要判断一个字符串是不是回文串，可以从外面开始判断，只有两种情况：
  • 第一个字符和最后一个字符相等，那么只需要判断里面的其余字符
  • 第一个字符和最后一个字符不相等，那么这个字符串就不是回文串，根据题目要求，可以去掉第一个字符或者最后一个字符再次进行判断，但是需要注意的是，只能删除一次
• 根据以上思路，我们首先从最外层开始判断，如果没发现有对应位置不相等的字符就判断是一个回文串
• 如果发现有对应位置不相等的字符，去掉最左边或者最右边的字符再进行一次是否是回文串的判断，如果还有对应位置不相等的字符，肯定就不满足题意了，返回false即可，如果没有对应位置不相等的字符，返回true即可

七【题目提示】

• $1<=s.length<=10^5$
• $s由小写英文字母组成$

八【时间频度】

• 时间复杂度：$O(n)$，其中$n$为传入字符串长度
• 空间复杂度：$O(1)$

九【代码实现】

1. Java语言版

class Solution {public boolean validPalindrome(String s) {int left = 0;int right = s.length() - 1;while(left < right){if(s.charAt(left) != s.charAt(right)){return isPalindrome(s,left + 1,right) || isPalindrome(s,left,right - 1);}left++;right--;}return true;}public boolean isPalindrome(String s,int i,int j){while(i < j){if(s.charAt(i) != s.charAt(j)){return false;}i++;j--;}return true;}
}

2. C语言版

bool isParlindrome(char *s,int i,int j)
{while(i < j){if(s[i] != s[j]){return false;}i++;j--;}return true;
}bool validPalindrome(char * s)
{int left = 0;int right = strlen(s) - 1;while(left < right){if(s[left] != s[right]){return isParlindrome(s,left + 1,right) || isParlindrome(s,left,right - 1);}left++;right--;}return true;
}

3. Python版

class Solution:def validPalindrome(self, s: str) -> bool:def isPalindrome(i,j):while i < j:if s[i] != s[j]:return Falsei += 1j -= 1return Trueleft = 0right = len(s) - 1while left < right:if s[left] != s[right]:return isPalindrome(left + 1,right) or isPalindrome(left,right - 1)left += 1right -= 1return True

十【提交结果】

1. Java语言版
   

2. C语言版
   

3. Python语言版