class Solution {
public:
bool validPalindrome(string s) {
}
};
680. 验证回文字符串 Ⅱ
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: s = "aba" 输出: true
示例 2:
输入: s = "abca" 输出: true 解释: 你可以删除c字符。
示例 3:
输入: s = "abc" 输出: false
提示:
1 <= s.length <= 105s 由小写英文字母组成相似题目
原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2.5 MB, 提交时间: 2025-02-03 09:12:18
impl Solution {
fn is_palindrome(s: &[u8]) -> bool {
let mut i = 0;
let mut j = s.len() - 1;
while i < j {
if s[i] != s[j] {
return false;
}
i += 1;
j -= 1;
}
true
}
pub fn valid_palindrome(s: String) -> bool {
let s = s.as_bytes();
let mut i = 0;
let mut j = s.len() - 1;
while i < j {
if s[i] != s[j] {
// 删除 s[i] 或者 s[j]
return Self::is_palindrome(&s[i + 1..=j]) || Self::is_palindrome(&s[i..j]);
}
i += 1;
j -= 1;
}
true // s 本身就是回文串
}
}
javascript 解法, 执行用时: 8 ms, 内存消耗: 56.6 MB, 提交时间: 2025-02-03 09:12:04
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s, i, j) {
while (i < j) {
if (s[i] !== s[j]) {
return false;
}
i++;
j--;
}
return true;
};
var validPalindrome = function(s) {
let i = 0, j = s.length - 1;
while (i < j) {
if (s[i] !== s[j]) {
// 删除 s[i] 或者 s[j]
return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
}
i++;
j--;
}
return true; // s 本身就是回文串
};
cpp 解法, 执行用时: 0 ms, 内存消耗: 21.8 MB, 提交时间: 2025-02-03 09:11:50
class Solution {
bool isPalindrome(string& s, int i, int j) {
while (i < j) {
if (s[i] != s[j]) {
return false;
}
i++;
j--;
}
return true;
}
public:
bool validPalindrome(string s) {
int i = 0, j = s.size() - 1;
while (i < j) {
if (s[i] != s[j]) {
// 删除 s[i] 或者 s[j]
return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
}
i++;
j--;
}
return true; // s 本身就是回文串
}
};
java 解法, 执行用时: 4 ms, 内存消耗: 44.9 MB, 提交时间: 2025-02-03 09:11:33
class Solution {
public boolean validPalindrome(String s) {
int i = 0;
int j = s.length() - 1;
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
// 删除 s[i] 或者 s[j]
return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
}
i++;
j--;
}
return true; // s 本身就是回文串
}
private boolean isPalindrome(String s, int i, int j) {
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
}
python3 解法, 执行用时: 35 ms, 内存消耗: 17.8 MB, 提交时间: 2025-02-03 09:11:19
class Solution:
def isPalindrome(self, s: str) -> bool:
return s == s[::-1]
def validPalindrome(self, s: str) -> bool:
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
# 删除 s[i] 或者 s[j]
return self.isPalindrome(s[i + 1: j + 1]) or self.isPalindrome(s[i: j])
i += 1
j -= 1
return True # s 本身就是回文串
golang 解法, 执行用时: 20 ms, 内存消耗: 6.5 MB, 提交时间: 2021-06-21 16:08:50
func validPalindrome(s string) bool {
low, high := 0, len(s) - 1
for low < high {
if s[low] == s[high] {
low++
high--
} else {
flag1, flag2 := true, true
// 排除高位, 剩余是否回文
for i, j := low, high - 1; i < j; i, j = i + 1, j - 1 {
if s[i] != s[j] {
flag1 = false
break
}
}
// 排除低位, 剩余是否回文
for i, j := low + 1, high; i < j; i, j = i + 1, j - 1 {
if s[i] != s[j] {
flag2 = false
break
}
}
return flag1 || flag2
}
}
return true
}