删除一个字母的回文

描述

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

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

样例:

Given s = "aba" return true

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

题目分析:

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

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')
);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

  1. 递归解法:
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')
);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

  1. 设置一个变量允许一次不同
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')
);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

代码地址

github 算法仓库地址

2018.8.12

Last Updated: 9/7/2018, 2:54:53 PM