680. Valid Palindrome II

Problem:

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.

Analysis:

leetcode 面经真准。这道题是fb最近的电面原题。

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class Solution { public boolean validPalindrome(String s) { if (s == null || s.length() == 0) return false; int l = 0, r = s.length() - 1; while (l < r) { if (s.charAt(l) == s.charAt(r)) { l++; r--; } else return isPalindrome(s, l+1, r) || isPalindrome(s, l, r - 1); } return true; } private boolean isPalindrome(String s, int l, int r) { while (l < r ) { if (s.charAt(l) != s.charAt(r)) return false; l++; r--; } return true; } }