680.验证回文字符串2.md

680. 验证回文字符串 Ⅱ

url

题目

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

输入: "aba"
输出: True
输入: "abca"
输出: True
解释: 你可以删除c字符。

方法

• 普通判断回文串用前后双指针即可，但是，难点在于如果去删除一个元素后的字符串是不是回文串
• 如果前后指针的元素不相等，此时子串的范围（i+1，j）或（j-1）的俩子串只要任意一个是，则结果是
• 否则，则不是

code

js

let validPalindrome = s => {
    let i = 0, j = s.length - 1;
    while (i < j) {
        if (s[i] !== s[j]) {
            return isValid(s, i+1, j) || isValid(s, i, j - 1);
        }
        i++;
        j--;
    }
    return true;
};
let isValid = (s, i, j) => {
    while (i < j) {
        if (s[i] !== s[j])
            return false;
        i++;
        j--;
    }
    return true;
};
console.log(validPalindrome("aba"))
console.log(validPalindrome("abca"))

go

func validPalindrome(s string) bool {
	isValid := func (s string, i int, j int) bool {
		for i < j {
		if s[i] != s[j] {
		return false
	}
		i++
		j--
	}
		return true
	}
	i, j := 0, len(s) - 1
	for i < j {
		if s[i] != s[j] {
			return isValid(s, i + 1, j) || isValid(s, i, j - 1)
		}
		i++
		j--
	}
	return true
}

java

class Solution {
    public boolean validPalindrome(String s) {
        int i =0, j = s.length() - 1;
        while(i < j) {
            if(s.charAt(i) != s.charAt(j)) {
                return isValid(s, i+1, j) || isValid(s, i, j-1);
            }
            i++;
            j--;
        }
        return true;
    }
    public boolean isValid(String s, int i, int j) {
        while(i < j) {
            if(s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}