description

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

 

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.

submission

// intuition: find the first unmatching pair of chars
// remove either of them and check the rest
impl Solution {
    pub fn valid_palindrome(s: String) -> bool {
        // remove the matching chars from both side
        // returns the remaining slice
        fn unmatch(mut s: &[u8]) -> &[u8] {
            loop {
                match s {
                    [l, rest @ .., r] if l == r => s = rest,
                    rest => return rest,
                }
            }
        }

        let s = s.as_bytes();
        match unmatch(s) {
            // length of 0,1,2 means success
            &[] | &[_] | &[_, _] => true,
            rest => {
                // delete unmatching char from either end and try again
                unmatch(&rest[1..]).len() < 2
                    || unmatch(&rest[..rest.len() - 1]).len() < 2
            }
        }
    }
}