Welcome to Subscribe On Youtube

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.

  • 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;
        }
    }
    
    ############
    
    class Solution {
        public boolean validPalindrome(String s) {
            for (int i = 0, j = s.length() - 1; i < j; ++i, --j) {
                if (s.charAt(i) != s.charAt(j)) {
                    return check(s, i + 1, j) || check(s, i, j - 1);
                }
            }
            return true;
        }
    
        private boolean check(String s, int i, int j) {
            for (; i < j; ++i, --j) {
                if (s.charAt(i) != s.charAt(j)) {
                    return false;
                }
            }
            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:
        def validPalindrome(self, s: str) -> bool:
            def check(i, j):
                while i < j:
                    if s[i] != s[j]:
                        return False
                    i, j = i + 1, j - 1
                return True
    
            i, j = 0, len(s) - 1
            while i < j:
                if s[i] != s[j]:
                    return check(i, j - 1) or check(i + 1, j)
                i, j = i + 1, j - 1
            return True
    
    ############
    
    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
    
    
  • func validPalindrome(s string) bool {
    	check := func(i, j int) bool {
    		for ; i < j; i, j = i+1, j-1 {
    			if s[i] != s[j] {
    				return false
    			}
    		}
    		return true
    	}
    	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
    		if s[i] != s[j] {
    			return check(i+1, j) || check(i, j-1)
    		}
    	}
    	return true
    }
    
  • function validPalindrome(s: string): boolean {
        for (let i: number = 0, j = s.length - 1; i < j; ++i, --j) {
            if (s.charAt(i) != s.charAt(j)) {
                return (
                    isPalinddrome(s.slice(i, j)) ||
                    isPalinddrome(s.slice(i + 1, j + 1))
                );
            }
        }
        return true;
    }
    
    function isPalinddrome(s: string): boolean {
        for (let i: number = 0, j = s.length - 1; i < j; ++i, --j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
    
    
  • /**
     * @param {string} s
     * @return {boolean}
     */
    var validPalindrome = function (s) {
        let check = function (i, j) {
            for (; i < j; ++i, --j) {
                if (s.charAt(i) != s.charAt(j)) {
                    return false;
                }
            }
            return true;
        };
        for (let i = 0, j = s.length - 1; i < j; ++i, --j) {
            if (s.charAt(i) != s.charAt(j)) {
                return check(i + 1, j) || check(i, j - 1);
            }
        }
        return true;
    };
    
    

All Problems

All Solutions