跳转至

2330. 验证回文串 IV 🔒

题目描述

给你一个下标从 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$ 的长度。

1
2
3
4
5
6
7
8
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
}

评论