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:

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

Solution(javascript)

// O(n^2)的解法显而易见，O(n) 的解法该如何去考虑
const validPalindrome = function (s = '') {
  const is = (left, right) => {
    for (let i = left; i <= Math.floor((left + right) / 2); i++) {
      if (s[i] !== s[right - (i - left)]) {
        return false
      }
    }
    return true
  }

  for (let i = 0; i <= Math.floor(s.length / 2); i++) {
    const right = s.length - 1 - i
    if (s[i] !== s[right]) {
      return is(i, right - 1) || is(i + 1, right)
    }
  }
  return true
}