LeetCode： Valid Palindrome II

Question

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

Solution#1

def valid_palindrome(s)
  return true if is_palindrome?(s)
  length = s.length-1

  (0...s.length).each do |i|
    left = s[i]
    right = s[length-i]

    if left != right
      return is_palindrome?(s[i+1..length-i]) || is_palindrome?(s[i..length-i-1])
    end
  end
end

def is_palindrome?(s)
  s == s.reverse
end

Solution#2

def valid_palindrome(s)
  # odd palindrome
  # even palindrome
  # odd non-palindrome -> even palindrome
  # even non-palindrome -> odd palindrome
  removed = false
  left = 0
  right = s.length - 1

  while left < right
    # puts "left: #{s[left]}, #{left}, right: #{s[right]},  #{right}"
    if s[left] != s[right]
      if !removed
        if s[left + 1] == s[right]
          left += 1
          removed = true
        elsif s[left] == s[right - 1]
          right -= 1
          removed = true
        else
          return false
        end
      else
        if s[left - 2] == s[right]
          left -= 2
        else
          return false
        end
      end
    end
      left += 1
      right -= 1
  end
  true
end