526互联

[LeetCode] 2330. Valid Palindrome IV

发布时间 2023-07-20 07:21:12作者: CNoodle

You are given a 0-indexed string s consisting of only lowercase English letters. In one operation, you can change any character of s to any other character.

Return true if you can make s a palindrome after performing exactly one or two operations, or return false otherwise.

Example 1:

Input: s = "abcdba"
Output: true
Explanation: One way to make s a palindrome using 1 operation is:
- Change s[2] to 'd'. Now, s = "abddba".
One operation could be performed to make s a palindrome so return true.

Example 2:

Input: s = "aa"
Output: true
Explanation: One way to make s a palindrome using 2 operations is:
- Change s[0] to 'b'. Now, s = "ba".
- Change s[1] to 'b'. Now, s = "bb".
Two operations could be performed to make s a palindrome so return true.

Example 3:

Input: s = "abcdef"
Output: false
Explanation: It is not possible to make s a palindrome using one or two operations so return false.

Constraints:

  • 1 <= s.length <= 105
  • s consists only of lowercase English letters.

有效的回文 IV。

题意是给一个字符串，你只能修改最多两处，请判断你是否能将这个字符串修改成一个回文串。

思路是双指针从两边往中间逼近，应该算是 easy 题。直接给代码。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public boolean makePalindrome(String s) {
 3         int left = 0;
 4         int right = s.length() - 1;
 5         int k = 2;
 6         while (left < right) {
 7             if (s.charAt(left) != s.charAt(right)) {
 8                 k--;
 9             }
10             if (k < 0) {
11                 return false;
12             }
13             left++;
14             right--;
15         }
16         return true;
17     }
18 }

 

LeetCode 题目总结