IT评测·应用市场-qidao123.com

标题: LeetCode：1328. 破坏回文串（贪心 Java） [打印本页]

---

作者: 伤心客    时间: 2025-3-6 11:20
标题: LeetCode：1328. 破坏回文串（贪心 Java）
目录
1328. 破坏回文串
题目形貌：
实现代码与解析：
贪心
原理思路：

---

1328. 破坏回文串

题目形貌：

        给你一个由小写英文字母组成的回文字符串 palindrome ，请你将此中 一个 字符用恣意小写英文字母更换，使得结果字符串的 字典序最小 ，且 不是 回文串。
请你返回结果字符串。如果无法做到，则返回一个 空串 。
如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样界说：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符严格小于 b 中的对应字符。比方，"abcc” 字典序比 "abcd" 小，由于不同的第一个位置是在第四个字符，显然 'c' 比 'd' 小。

示例 1：

1. <strong>输入：</strong>palindrome = "abccba"
2. <strong>输出：</strong>"aaccba"
3. <strong>解释：</strong>存在多种方法可以使 "abccba" 不是回文，例如 "<em><strong>z</strong></em>bccba", "a<em><strong>a</strong></em>ccba", 和 "ab<em><strong>a</strong></em>cba" 。
4. 在所有方法中，"aaccba" 的字典序最小。

复制代码

示例 2：

1. <strong>输入：</strong>palindrome = "a"
2. <strong>输出：</strong>""
3. <strong>解释：</strong>不存在替换一个字符使 "a" 变成非回文的方法，所以返回空字符串。

复制代码

提示：

• 1 <= palindrome.length <= 1000
  
• palindrome 只包罗小写英文字母。
  

实现代码与解析：

贪心

1. class Solution {
2.     public String breakPalindrome(String palindrome) {
3.         
4.         int n = palindrome.length();
5.         if (n == 1) {
6.             return "";
7.         }
8.         char[] cs = palindrome.toCharArray();
9.         for (int i = 0; i * 2 + 1 < n; i++) {
10.             if (cs[i] != 'a') {
11.                 cs[i] = 'a';
12.                 return new String(cs);
13.             }
14.         }
15.         cs[n - 1] = 'b';
16.         return new String(cs);
17.     }
18. }

复制代码

原理思路：

        n = 1，无论如何换都是回文。遍历字符串一半，如果不为a换成a。如果前半部门全为a，那么根据回文特性，该字符串全为a，只有把最后一个字符修改为小于a的第一个值b即可。


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com (https://dis.qidao123.com/)

Powered by Discuz! X3.4