680. Valid Palindrome II

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters.

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
26
27
28
29
30
31
32
33

class Solution {
    public boolean validPalindrome(String s) {
        return palindrom(s, 0);
    }
    
    boolean palindrom(String s, int count) {
        int i = 0; 
        int n = s.length();
        
        while (i < n / 2) {
            char c1 = s.charAt(i);
            char c2 = s.charAt(n - i - 1);
            
            if (c1 == c2) {
                i++;
                continue;
            } else {
                if (count == 0) {
                    StringBuilder sb1 = new StringBuilder(s);
                    sb1.deleteCharAt(i);
                    boolean res1 = palindrom(sb1.toString(), 1);
                    if (res1) return true;
                    StringBuilder sb2 = new StringBuilder(s);
                    sb2.deleteCharAt(n - i - 1);
                    return palindrom(sb2.toString(), 1);
                }
                return false;
            }
        }
        
        return true;
    }
}

Solution 2021-11-21

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

class Solution {
    public boolean validPalindrome(String s) {
        return validatePalindrom(s, 1, 0, s.length() - 1);
    }
    
    boolean validatePalindrom(String s, int deleted, int lo, int hi) {
        while (lo < hi) {
            if (s.charAt(lo) == s.charAt(hi)) {
                lo++;
                hi--;
            } else {
                if (deleted == 0) {
                    return false;
                }
                return 
                    validatePalindrom(s, 0, lo + 1, hi) ||                                                   validatePalindrom(s, 0, lo, hi - 1);
            }
        }
        
        return true;
    }
}

Solution 2022-01-22

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

class Solution {
    public boolean validPalindrome(String s) {
        char[] symbols = s.toCharArray();
        return validPalindrome(symbols, 0, s.length() - 1, 1);
    }
    
    boolean validPalindrome(char[] symbols, int i, int j, int count) {
        while (i < j) {
            if (symbols[i] == symbols[j]) {
                i++;
                j--;
                continue;
            } else {
                if (count > 0) {
                    return validPalindrome(symbols, i, j - 1, 0) || validPalindrome(symbols, i + 1, j, 0);
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}