Title

the problem link

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.

用greedy

Solution

//cpp:
class Solution {
public:
	bool ispalindrome(string s, int i, int j) {
		for (; i < j; i++, j--) {
			if (s[i] != s[j])
				return false;
		}
		return true;
	}
	bool validPalindrome(string s) {
		bool is = false;
		for (int i = 0; i < s.length() / 2; i++) {
			if (s[i] != s[s.length() - i - 1]) {
				return (ispalindrome(s, i + 1, s.length() - i - 1) || ispalindrome(s, i, s.length() - i - 2));
			}
		}
        return true;
	}
};

Approach #2: Greedy [Accepted] Intuition

If the beginning and end characters of a string are the same (ie. s[0] == s[s.length - 1]), then whether the inner characters are a palindrome (s[1], s[2], …, s[s.length - 2]) uniquely determines whether the entire string is a palindrome.

Algorithm

Suppose we want to know whether s[i], s[i+1], …, s[j] form a palindrome. If i >= j then we are done. If s[i] == s[j] then we may take i++; j–. Otherwise, the palindrome must be either s[i+1], s[i+2], …, s[j] or s[i], s[i+1], …, s[j-1], and we should check both cases.

class Solution {
    public boolean isPalindromeRange(String s, int i, int j) {
        for (int k = i; k <= i + (j - i) / 2; k++) {
            if (s.charAt(k) != s.charAt(j - k + i)) return false;
        }
        return true;
    }
    public boolean validPalindrome(String s) {
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
                int j = s.length() - 1 - i;
                return (isPalindromeRange(s, i+1, j) ||
                        isPalindromeRange(s, i, j-1));
            }
        }
        return true;
    }
}