[LeetCode]Valid Palindrome II

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

原题

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.

思路

水题。
判断是否是回文字符串最简单的方式就是从左右两端逐步向中心逼近(双指针),如下代码:

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来分隔,并产生一些拷贝。

原题:https://leetcode.com/problems/valid-palindrome-ii/

相关题目:https://leetcode.com/problems/valid-palindrome/

文章来源:胡小旭 => [LeetCode]Valid Palindrome II


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: C/C++, 技术, 算法, 编程 | 标签: , , , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。