[LeetCode] 680. Valid Palindrome II

轉自LeetCode

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Input: "aba"
Output: True

Example 2:

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

Note:

1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

<Solution>

125. Valid Palindrome 的衍生題

想法如下

• 一樣從頭尾檢查是否是 palindrome，如果發現不是，因為題目說可以刪除一個字元，所以會有兩種情況，假如位置 i 和位置 j 是不同字元

• 第一種情況，刪除位置 j 的字元，所以檢查 i, i+1 ... , j-1 是不是 palindrom

• 第二種情況，刪除位置 i 的字元，所以檢查 i+1, i+2 ... , j 是不是 palindrom

• 如果上述兩種情況都是 false，就直接回傳 false (因為題目說只能刪除一個字元，所以只要檢查一次不同的地方就可以了)

code 如下

Java

kotlin