Play this article
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
}
}