Last Updated on 2022-04-02 by Clay
題目
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 <= 105sconsists of lowercase English letters.
題目輸入一字串，我們需要在最多能刪除一個字元的情況下，判斷該字串是否為回文（palindrome）。
解題思路
兩端點解法
我們可以透過判斷字串左右端點的字元是否相同，來判斷該字串是否是回文；而當左右端點不同的情況，我們可以分別判斷刪去左右端點後是否為回文。
我在實作中是以一個變數 count 來紀錄刪除次數，一但刪除次數大於 1，則直接判斷非回文的情況。
但是只要存在一種刪除後為回文的情況，則代表該字串是回文的。
兩端點解法複雜度
由於我們需要遍歷整個陣列，故時間複雜度為 O(n)。
| Time complexity | O(n) |
| Space complexity | O(1) |
兩端點解法 C++ 範例程式碼
class Solution {
public:
bool matching(string& s, int left, int right, int count) {
// Base case
if (count > 1) return false;
while (left < right) {
if (s[left] == s[right]) {
++left;
--right;
}
else {
return (matching(s, left+1, right, count+1) || matching(s, left, right-1, count+1));
}
}
return true;
}
bool validPalindrome(string s) {
// Init
int left = 0;
int right = s.size() - 1;
// Matching
return matching(s, left, right, 0);
}
};兩端點解法 Python 範例程式碼
class Solution:
def matching(self, s, left, right, count):
# Base case
if count > 1: return False
while left < right:
if s[left] == s[right]:
left += 1
right -= 1
else:
return self.matching(s, left+1, right, count+1) or self.matching(s, left, right-1, count+1)
return True
def validPalindrome(self, s: str) -> bool:
# Init
left = 0
right = len(s) - 1
return self.matching(s, left, right, 0)