Formatted question description: https://leetcode.ca/all/680.html

680. Valid Palindrome II (Easy)

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.

Companies:
Facebook, Google, Yahoo

Related Topics:
String

Similar Questions:

Solution 1.

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

// Time: O(N)
// Space: O(1)
class Solution {
private:
    bool isPalindrome(string s, int i, int j) {
        while (i < j) {
            if (s[i++] != s[j--]) return false;
        }
        return true;
    }
public:
    bool validPalindrome(string s) {
        int i = 0, j = s.size() - 1, del = 1;
        for (; i < j; ++i, --j) {
            if (s[i] == s[j]) continue;
            if (isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1)) return true;
            return false;
        }
        return true;
    }
};

Java

class Solution {
    public boolean validPalindrome(String s) {
        int low = 0, high = s.length() - 1;
        while (low < high) {
            char c1 = s.charAt(low), c2 = s.charAt(high);
            if (c1 == c2) {
                low++;
                high--;
            } else {
                boolean flag1 = true, flag2 = true;
                for (int i = low, j = high - 1; i < j; i++, j--) {
                    char c3 = s.charAt(i), c4 = s.charAt(j);
                    if (c3 != c4) {
                        flag1 = false;
                        break;
                    }
                }
                for (int i = low + 1, j = high; i < j; i++, j--) {
                    char c3 = s.charAt(i), c4 = s.charAt(j);
                    if (c3 != c4) {
                        flag2 = false;
                        break;
                    }
                }
                return flag1 || flag2;
            }
        }
        return true;
    }
}

All Problems

All Solutions