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;
        }
    }
    
  • // OJ: https://leetcode.com/problems/valid-palindrome-ii/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        bool validPalindrome(string s) {
            int i = 0, j = s.size() - 1;
            while (i < j && s[i] == s[j]) ++i, --j;
            if (i >= j) return true;
            auto valid = [&](int i, int j) {
                while (i < j && s[i] == s[j]) ++i, --j;
                return i >= j;
            };
            return valid(i + 1, j) || valid(i, j - 1);
        }
    };
    
  • class Solution(object):
        def validPalindrome(self, s):
            """
            :type s: str
            :rtype: bool
            """
            isPalindrome = lambda s: s == s[::-1]
            strPart = lambda s, x: s[:x] + s[x + 1:]
            left = 0
            right = len(s) - 1
            while left < right:
                if s[left] != s[right]:
                    return isPalindrome(strPart(s, left)) or isPalindrome(strPart(s, right))
                left += 1
                right -= 1
            return True
    
    

All Problems

All Solutions