leetcode680：验证回文串 II（valid-palindrome-ii）

[carloscn]

问题描述

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1： 输入：s = "aba" 输出：true

示例 2： 输入：s = "abca" 输出：true 解释：你可以删除字符 'c' 。

示例 3： 输入：s = "abc" 输出：false

提示： 1 <= s.length <= 105 s 由小写英文字母组成

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/valid-palindrome-ii

[carloscn]

问题分析

C语言版本

static int32_t valid_palindrome_ii(const char *in_str, bool *result)
{
    int32_t ret = 0;
    size_t len = 0, i = 0, j = 0;
    char *str = NULL;
    bool tol = false;

    UTILS_CHECK_PTR(in_str);
    UTILS_CHECK_PTR(result);
    UTILS_CHECK_LEN(len = strlen(in_str));

    j = len - 1;
    str = strdup(in_str);
    UTILS_CHECK_PTR(str);

    *result = false;
    while (i != j) {
        if (str[i] != str[j]) {
            if (tol == false) {
                // try left
                if (str[i + 1] == str[j]) {
                    i++;
                    tol = true;
                    continue;
                }
                // try right
                else if (str[i] == str[j - 1]) {
                    j --;
                    tol = true;
                    continue;
                } else {
                    goto finish;
                }
            } else {
                goto finish;
            }
        }
        i ++;
        j --;
        if (j - i == 1) {
            break;
        }
    }

    *result = true;

finish:
    if (str != NULL)
        free(str);
    return ret;
}

rust版本

fn valid_palindrome_ii(in_str:&str) -> bool
{
    let len:usize = in_str.len();
    let mut tol:bool = false;
    let binding = String::from(in_str);
    let char_list = binding.as_bytes();
    let mut i:usize = 0;
    let mut j:usize = len - 1;

    while i != j {
        if char_list[i] != char_list[j] {
            if tol == false {
                if char_list[i + 1] == char_list[i] {
                    i += 1;
                    tol = true;
                    continue;
                } else if char_list[i] == char_list[j - 1] {
                    j -= 1;
                    tol = true;
                    continue;
                } else {
                    return false;
                }
            } else {
                return false;
            }

        }
        i += 1;
        j -= 1;
        if (j - i) == 1 {
            break;
        }
    }

    return true;
}

[carloscn]

code

https://github.com/carloscn/structstudy/blob/master/c_programming/str/n37_valid_palindrome_ii_680.c https://github.com/carloscn/structstudy/blob/master/rust_programming/str/src/n37_valid_palindrome_ii_680.rs