[LeetCode] 680. Valid Palindrome II

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.

Thought process:

Two pointers. One starts from the beginning and one from the end. Use a flag to check if a character has been deleted. If there's a character difference and no deletion has happened yet, set the flag to true and call recursively.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public boolean validPalindrome(String s) { return validPalindrome(s, 0, s.length() - 1, false); } private boolean validPalindrome(String s, int left, int right, boolean deleted) { while (left < right) { if (s.charAt(left) != s.charAt(right)) { if (deleted) { return false; } return validPalindrome(s, left + 1, right, true) || validPalindrome(s, left, right - 1, true); } left++; right--; } return true; } }

Time complexity: O(n).