算法-判断字符回文

描述

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

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

样例：

Given s = "aba" return true

Given s = "abca" return true // delete c

题目分析：

• 如果单单是回文的话，就很简单了: s === [...s].reverse().join(""); // 翻转字符串与原字符相比 // 实际上这里做了很多步操作，字符转数组 翻转数组 再转字符串，所以这里性能也不是很好 // 如果对性能要求比较高的话，还是通过循环从两侧向中间逐一比较，会更好一点
• 题目中还有一个要求：删除一个字符，也就是允许一个字符的不同。
• 下面我们的解法主体思路就是通过循环，从两侧向中间比较，然后解决当出现不同的情况，如何保证只允许出现一个不同。

code:

1. 出现一处不同 将值传入一个新函数，再进行判断字符串： 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')) 这个写好之后，我在想能不能通过递归的形式来解决，为什么要创建第二个函数？
2. 递归解法： 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')) 相对于上个解法这里就是多设置了一个变量，然后将两方区分开来，但是这样递归我还是觉得太傻了，所以在想你能不能通过设置变量来处理？出现两次不同即失败。
3. 设置一个变量允许一次不同 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