Question

2330. 验证回文串 IV

English Version

题目描述

给你一个下标从 0 开始、仅由小写英文字母组成的字符串 s 。在一步操作中，你可以将 s 中的任一字符更改为其他任何字符。

如果你能在 恰 执行一到两步操作后使 s 变成一个回文，则返回 true ，否则返回 false 。

 

示例 1：

输入: s = "abcdba"
输出: true
解释: 能让 s 变成回文，且只用了一步操作的方案如下:
- 将 s[2] 变成 'd' ，得到 s = "abddba" 。
执行一步操作让 s 变成一个回文，所以返回 true 。

示例 2：

输入: s = "aa"
输出: true
解释: 能让 s 变成回文，且只用了两步操作的方案如下:
- 将 s[0] 变成 'b' ，得到 s = "ba" 。
- 将 s[1] 变成 'b' ，得到s = "bb" 。
执行两步操作让 s 变成一个回文，所以返回 true 。 

示例 3：

输入: s = "abcdef"
输出: false
解释: 不存在能在两步操作以内将 s 变成回文的办法，所以返回 false 。

 

提示：

• 1 <= s.length <= 105
• s 仅由小写英文字母组成

解法

方法一：双指针

我们可以使用双指针 $i$ 和 $j$，分别指向字符串的头尾，然后向中间移动，统计不同字符的个数，如果不同字符的个数大于 $2$，则返回 false，否则返回 true。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为字符串 $s$ 的长度。

class Solution:
  def makePalindrome(self, s: str) -> bool:
    i, j = 0, len(s) - 1
    cnt = 0
    while i < j:
      cnt += s[i] != s[j]
      i, j = i + 1, j - 1
    return cnt <= 2

class Solution {
  public boolean makePalindrome(String s) {
    int cnt = 0;
    int i = 0, j = s.length() - 1;
    for (; i < j; ++i, --j) {
      if (s.charAt(i) != s.charAt(j)) {
        ++cnt;
      }
    }
    return cnt <= 2;
  }
}

class Solution {
public:
  bool makePalindrome(string s) {
    int cnt = 0;
    int i = 0, j = s.size() - 1;
    for (; i < j; ++i, --j) {
      cnt += s[i] != s[j];
    }
    return cnt <= 2;
  }
};

func makePalindrome(s string) bool {
  cnt := 0
  i, j := 0, len(s)-1
  for ; i < j; i, j = i+1, j-1 {
    if s[i] != s[j] {
      cnt++
    }
  }
  return cnt <= 2
}

function makePalindrome(s: string): boolean {
  let cnt = 0;
  let i = 0;
  let j = s.length - 1;
  for (; i < j; ++i, --j) {
    if (s[i] != s[j]) {
      ++cnt;
    }
  }
  return cnt <= 2;
}