制作个人网站实例,个人网站能挂广告吗,潍坊优化网站,关于网站平台建设调研的函【LetMeFly】680.验证回文串 II#xff1a;两侧向中间#xff0c;不同就试删
力扣题目链接#xff1a;https://leetcode.cn/problems/valid-palindrome-ii/
给你一个字符串 s#xff0c;最多 可以从中删除一个字符。
请你判断 s 是否能成为回文字符串#xff1a;如果能…【LetMeFly】680.验证回文串 II两侧向中间不同就试删
力扣题目链接https://leetcode.cn/problems/valid-palindrome-ii/
给你一个字符串 s最多 可以从中删除一个字符。
请你判断 s 是否能成为回文字符串如果能返回 true 否则返回 false 。 示例 1
输入s aba
输出true示例 2
输入s abca
输出true
解释你可以删除字符 c 。示例 3
输入s abc
输出false 提示
1 s.length 105s 由小写英文字母组成
解题方法遍历
从两边到中间遍历字符串如果当前两个字符不相同就尝试删除其中的一个并判断删除后中间剩下的字符串是否是回文字符串。
如果删除一个或零个能成为回文字符串则返回true。
时间复杂度 O ( l e n ( s ) ) O(len(s)) O(len(s))空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C
/** Author: LetMeFly* Date: 2025-02-03 08:52:33* LastEditors: LetMeFly.xyz* LastEditTime: 2025-02-03 08:57:47*/
class Solution {
private:bool isOk(string s, int l, int r) {for (; l r; l, r--) {if (s[l] ! s[r]) {return false;}}return true;}
public:bool validPalindrome(string s) {for (int i 0, j s.size() - 1; i j; i, j--) {if (s[i] ! s[j]) {return isOk(s, i, j - 1) || isOk(s, i 1, j);}}return true;}
};Python Author: LetMeFly
Date: 2025-02-03 08:57:31
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-03 08:59:26class Solution:def isOk(self, s: str, l: int, r: int) - bool:while l r:if s[l] ! s[r]:return Falsel 1r - 1return Truedef validPalindrome(self, s: str) - bool:l, r 0, len(s) - 1while l r:if s[l] ! s[r]:return self.isOk(s, l, r - 1) or self.isOk(s, l 1, r)l 1r - 1return TrueJava
/** Author: LetMeFly* Date: 2025-02-03 08:57:34* LastEditors: LetMeFly.xyz* LastEditTime: 2025-02-03 09:01:29*/
class Solution {private boolean isOk(String s, int l, int r) {for (; l r; l, r--) {if (s.charAt(l) ! s.charAt(r)) {return false;}}return true;}public boolean validPalindrome(String s) {for (int l 0, r s.length() - 1; l r; l, r--) {if (s.charAt(l) ! s.charAt(r)) {return isOk(s, l, r - 1) || isOk(s, l 1, r);}}return true;}
}Go
/** Author: LetMeFly* Date: 2025-02-03 08:57:46* LastEditors: LetMeFly.xyz* LastEditTime: 2025-02-03 09:05:54*/
package mainfunc isOk_VP(s string, l, r int) bool {for ; l r; l, r l 1, r - 1 {if s[l] ! s[r] {return false}}return true
}func validPalindrome(s string) bool {for l, r : 0, len(s) - 1; l r; l, r l 1, r - 1 {if s[l] ! s[r] {return isOk_VP(s, l, r - 1) || isOk_VP(s, l 1, r)}}return true
}同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/145427404
