LeetCode 680. Valid Palindrome II

[quinnwencn]

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.

[quinnwencn]

Analysis

Solution written in Rust

impl Solution {
    pub fn valid_palindrome(s: String) -> bool {
        let vs = s.chars().collect::<Vec<char>>();
        let mut left = 0; 
        let mut right = vs.len() - 1;
        let mut jump = 1;
        while left < right {
            if vs[left] != vs[right] {
                return Self::helper(&vs, left, right - 1) || Self::helper(&vs, left + 1, right);
            }

            left += 1;
            right -= 1;
        }
        true
    }

    fn helper(s: &Vec<char>, mut left: usize, mut right: usize) -> bool {
        while left < right {
            if s[left] != s[right] {
                return false;
            }

            left += 1;
            right -= 1;
        }

        true
    }
}

Solution written in Cpp

class Solution {
public:
    bool validPalindrome(string s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                return helper(s, left, right - 1) || helper(s, left + 1, right);
            }

            left++;
            right--;
        }

        return true;
    }

    bool helper(const std::string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
};