算法_判断字符串回文

描述

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

该字符串仅包含小写字符a-z,字符串的最大长度为50000。

样例：

Given s = “aba” return true

Given s = “abca” return true // delete c

题目分析：

如果单单是回文的话，就很简单了:

s === [...s].reverse().join(""); // 翻转字符串与原字符相比
// 实际上这里做了很多步操作，字符转数组 翻转数组 再转字符串，所以这里性能也不是很好
// 如果对性能要求比较高的话，还是通过循环从两侧向中间逐一比较，会更好一点

题目中还有一个要求：删除一个字符，也就是允许一个字符的不同。
下面我们的解法主体思路就是通过循环，从两侧向中间比较，然后解决当出现不同的情况，如何保证只允许出现一个不同。

code:

出现一处不同将值传入一个新函数，再进行判断字符串：

const validPalindrome = s => {
    let left = 0;
    let right = s.length - 1;
    while (left < right) {
        if (s[left] !== s[right]) {
            // 左右两边字符都要尝试一下 一边返回true即可
            return isSubPalindrom(s, left + 1, right) || isSubPalindrom(s, left, right - 1); 
        }
        left++;
        right--;
    }
    return true; // 循环结束返回true
}
const isSubPalindrom = (s, left, right) => {
    while (left < right) {
        if (s[left] !== s[right]) {
            return false; // 再有不同之处 返回false
        }
        left++;
        right--;
    }
    return true; // 循环结束一直相等返回true
    // 并且left不小于right 直接返回right，说明不同之处只有一个
}
console.log('回文验证:', validPalindrome('abaacaaa'), validPalindrome('ab'), validPalindrome('abc'), validPalindrome('aabsjdbaa'))

这个写好之后，我在想能不能通过递归的形式来解决，为什么要创建第二个函数？

递归解法：

const validPalindrome = (s, left = 0, right = s.length - 1, type = 'first') => {
    if (type === 'first') {
        // 第一次进入允许出现一次不同
        while (left < right) {
            if (s[left] !== s[right]) {
                return validPalindrome(s, left + 1, right, 'second') || validPalindrome(s, left, right - 1, 'second'); // 左右两边都尝试一下 一边返回true即可
            }
            left++;
            right--;
        }
        return true; // 循环结束返回true
    } else {
        // 第二次 再有不同之处 返回false
        while (left < right) {
            if (s[left] !== s[right]) {
                return false; 
            }
            left++;
            right--;
        }
        return true; // 循环结束一直相等返回true
        // 并且left不小于right 直接返回right，说明不同之处只有一个
    }
}
console.log('回文验证:', validPalindrome('abaacaaa'), validPalindrome('ab'), validPalindrome('abc'), validPalindrome('aabsjdbaa'))

相对于上个解法这里就是多设置了一个变量，然后将两方区分开来，但是这样递归我还是觉得太傻了，所以在想你能不能通过设置变量来处理？出现两次不同即失败。

设置一个变量允许一次不同

const validPalindrome = s => {
    let removed = false;
    for (let [i, j] = [0, s.length - 1]; i < j; i++ , j--) {
        // 从两侧向中间递减 i- j-1 减到最后 i>j i=j 退出循环
        if (s[i] !== s[j]) { // 如果两侧不相同
            if (removed) { // 只允许一次不同
                return false;
            }
            if (s[i] === s[j - 1]) {
                // 转数组删除一个不同元素 下次直接return
                // s = [...s].splice(j, 1);
                // s = s.join(''); // 处理过的字符串
                j--;
                removed = true;
            } else if (s[i + 1] === s[j]) {
                // s = [...s].splice(i, 1);
                // s = s.join(''); // 处理过的字符串
                i++;
                removed = true;
            } else {
                // 上面两个else 右边-1 或左边+1相不相等 如果两边也不相等即false
                return false;
            }
        }
    }
    return true;
}
console.log('回文验证:', validPalindrome('abaacaaa'), validPalindrome('ab'), validPalindrome('abc'), validPalindrome('aabsjdbaa'))

代码地址

github 算法仓库地址

2018.8.12