[LeetCode]Valid Palindrome II
原題
Given a non-empty strings
, you may delete at most
one character. Judge whether you can make it a palindrome.
Example 1:
<b>Input:</b> "aba" <b>Output:</b> True
Example 2:
<b>Input:</b> "abca" <b>Output:</b> True <b>Explanation:</b> You could delete the character 'c'.
Note:
- The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
思路
水題。
判斷是否是迴文字串最簡單的方式就是從左右兩端逐步向中心逼近(雙指標),如下程式碼:
for (int i = 0; i < s.length(); ++i) { if (s[i] != s[s.length() - 1 - i]) return false; } return true;
題中指出可以最多刪除一個欄位,那麼當遇到左右不一致時會有兩個分支產生。即刪除左邊的字元,或者刪除右邊的字元。然後分別判斷產生的兩個子字串是否是迴文字串即可。
程式碼
class Solution { public: bool isValid(string s, int start, int end) { for (int i = start; i < (end - start + 1) / 2 + start; ++i) { if (s[i] != s[end - (i - start)]) return false; } return true; } bool validPalindrome(string s) { for (int i = 0; i < s.length() / 2; ++i) { if (s[i] != s[s.length() - i - 1]) { if (!isValid(s, i + 1, s.length() - i - 1) && !isValid(s, i, s.length() - i -2)) return false; break; } } return true; } };
複雜度
時間複雜度:O(n)
空間複雜度:O(n)
技巧
- 由於只有兩個分支,所以沒有必要利用棧來實現回溯法。
- 再產生兩個子字串時,可以使用兩個指標來指定子字串的範圍,而不是使用substr來分隔,併產生一些拷貝。