河南省住房与城乡建设部网站,丹徒网站,中企动力邮箱登陆入口,网站建设新一点网络文章目录一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【解题思路】七【题目提示】八【时间频度】九【代码实现】十【提交结果】一【题目类别】
贪心算法
二【题目难度】
简单
三【题目编号】
680.验证回文串 II
四【题目描述】
给你一个字…
文章目录一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【解题思路】七【题目提示】八【时间频度】九【代码实现】十【提交结果】一【题目类别】
贪心算法
二【题目难度】
简单
三【题目编号】
680.验证回文串 II
四【题目描述】
给你一个字符串 s最多 可以从中删除一个字符。请你判断 s 是否能成为回文字符串如果能返回 true 否则返回 false 。
五【题目示例】 示例 1 输入s “aba”输出true 示例 2 输入s “abca”输出true解释你可以删除字符 ‘c’ 。 示例 3 输入s “abc”输出false
六【解题思路】
利用贪心算法的思想由外到内逐层判断是否是回文串要判断一个字符串是不是回文串可以从外面开始判断只有两种情况 第一个字符和最后一个字符相等那么只需要判断里面的其余字符第一个字符和最后一个字符不相等那么这个字符串就不是回文串根据题目要求可以去掉第一个字符或者最后一个字符再次进行判断但是需要注意的是只能删除一次 根据以上思路我们首先从最外层开始判断如果没发现有对应位置不相等的字符就判断是一个回文串如果发现有对应位置不相等的字符去掉最左边或者最右边的字符再进行一次是否是回文串的判断如果还有对应位置不相等的字符肯定就不满足题意了返回false即可如果没有对应位置不相等的字符返回true即可
七【题目提示】
1s.length1051 s.length 10^51s.length105s由小写英文字母组成s 由小写英文字母组成s由小写英文字母组成
八【时间频度】
时间复杂度O(n)O(n)O(n)其中nnn为传入字符串长度空间复杂度O(1)O(1)O(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;}
}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;
}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十【提交结果】 Java语言版 C语言版 Python语言版
