Follow

Follow

·Apr 6, 2022·

680. Valid Palindrome II

題目敘述

Given a string `s`, return `true` if the `s` can be palindrome after deleting at most one character from it.

Example 1:

``````Input: s = "aba"
Output: true
``````

Example 2:

``````Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.
``````

Example 3:

``````Input: s = "abc"
Output: false
``````

Constraints:

• `1 <= s.length <= 10**5`
• `s` consists of lowercase English letters.

解法解析

解法範例

Go

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

JavaScript

``````/**
* @param {string} s
* @return {boolean}
*/
var validPalindrome = function (s) {
let i = 0,
j = s.length - 1;
while (i < j) {
if (s[i] !== s[j]) {
return checkPalindrome(s, i + 1, j) || checkPalindrome(s, i, j - 1);
}
i++;
j--;
}
return true;
};

const checkPalindrome = (s, i, j) => {
while (i < j) {
if (s[i] !== s[j]) return false;
i++;
j--;
}
return true;
};
``````

Kotlin

``````class Solution {
fun validPalindrome(s: String): Boolean {
var i = 0
var j = s.length - 1
while (i < j) {
if (s[i] != s[j]) {
return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1)
}
i++
j--
}
return true
}

fun isPalindrome(s: String, i: Int, j: Int): Boolean {
var i = i
var j = j
while (i < j) {
if (s[i] != s[j]) {
return false
}
i++
j--
}
return true
}
}
``````

PHP

``````class Solution
{

/**
* @param String \$s
* @return Boolean
*/
function validPalindrome(\$s)
{
\$i = 0;
\$j = strlen(\$s) - 1;
while (\$i < \$j) {
if (\$s[\$i] != \$s[\$j]) {
return \$this->checkPalindrome(\$s, \$i + 1, \$j) || \$this->checkPalindrome(\$s, \$i, \$j - 1);
}
\$i++;
\$j--;
}
return true;
}

function checkPalindrome(\$s, \$i, \$j)
{
while (\$i < \$j) {
if (\$s[\$i] != \$s[\$j]) {
return false;
}
\$i++;
\$j--;
}
return true;
}
}
``````

Python

``````class Solution:
def validPalindrome(self, s: str) -> bool:
def check_palindrome(s, i, j):
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1

return True

i = 0
j = len(s) - 1
while i < j:
# Found a mismatched pair - try both deletions
if s[i] != s[j]:
return check_palindrome(s, i, j - 1) or check_palindrome(s, i + 1, j)
i += 1
j -= 1

return True
``````

Rust

``````
``````

Swift

``````class Solution {
func validPalindrome(_ s: String) -> Bool {
let s = Array(s)
var i = 0
var j = s.count - 1
while i < j {
if s[i] != s[j] {
return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1)
}
i += 1
j -= 1
}
return true
}

func isPalindrome(_ s: [Character], _ i: Int, _ j: Int) -> Bool {
var i = i
var j = j
while i < j {
if s[i] != s[j] {
return false
}
i += 1
j -= 1
}
return true
}
}
``````