[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).

Comments

Popular posts from this blog

[LeetCode] 269. Alien Dictionary

[HackerRank] Roads and Libraries

[LeetCode] 425. Word Squares