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
  }
}

LeetCode Solution, Easy, 680. Valid Palindrome II

Comments

LeetCode Solution

More from this blog

如何開始入門軟體工程領域 - 名詞解釋（長期更新）

我的 MacBook Pro (Apple Silicon) 設定

ChatGPT 下的發展預想

一些覺得有用的工具蒐藏

LeetCode Solution, Medium, 607. Sales Person

680. Valid Palindrome II

題目敘述

題目翻譯

解法解析

解法範例

Go

JavaScript

Kotlin

PHP

Python

Rust

Swift

Command Palette

Comments

LeetCode Solution

More from this blog

680. Valid Palindrome II

題目敘述

題目翻譯

解法解析

解法範例

Go

JavaScript

Kotlin

PHP

Python

Rust

Swift