Valid Palindrome II

https://leetcode.com/problems/valid-palindrome-ii/description/

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:

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

Thoughts

问给定字符串至多删去一个字符能否构成回文。只有一个字符不满足的话当遇到那个字符时跳过它就还是palindrome，跳过的方式有从左或右跳过。

Code

/*
 * @lc app=leetcode id=680 lang=cpp
 *
 * [680] Valid Palindrome II
 */

// @lc code=start
class Solution {
public:
    bool validPalindrome(string s) {
        const auto palind = [&](int l, int r) {
            while (l < r) {
                if (s[l] != s[r]) return false;
                else {
                    ++l;
                    --r;
                }
            }
            return true;
        };
        for (int l = 0, r = s.length() - 1; l < r; ++l, --r) {
            if (s[l] != s[r]) {
                return palind(l + 1, r) || palind(l, r - 1);
            }
        }
        return true;
    }
};
// @lc code=end

class Solution {
    private boolean isPalin(String s, int start, int end) {
        for (; start < end; start++, end--) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
        }
        return true;
    }

    public boolean validPalindrome(String s) {
        for (int l = 0, r = s.length() - 1; l < r; l++, r--) {
            if (s.charAt(l) == s.charAt(r)) {
                continue;
            } else {
                return isPalin(s, l + 1, r) || isPalin(s, l, r - 1);
            }
        }

        return true;
    }
}

Analysis

时间O(N).