删除一个字母的回文 | 前端进阶积累

# 删除一个字母的回文

# 描述

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

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

# 样例：

Given s = "aba" return true

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

# 题目分析：

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

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

1
2
3

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

# 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')
);

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

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

递归解法：

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

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

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

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

2018.8.12