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