比较好的商城网站设计,myeclipse怎样做网站,帮您做网站,支付集成文件放在网站哪里【LetMeFly】1328.破坏回文串#xff1a;贪心
力扣题目链接#xff1a;https://leetcode.cn/problems/break-a-palindrome/
给你一个由小写英文字母组成的回文字符串 palindrome #xff0c;请你将其中 一个 字符用任意小写英文字母替换#xff0c;使得结果字符串的 字典…【LetMeFly】1328.破坏回文串贪心
力扣题目链接https://leetcode.cn/problems/break-a-palindrome/
给你一个由小写英文字母组成的回文字符串 palindrome 请你将其中 一个 字符用任意小写英文字母替换使得结果字符串的 字典序最小 且 不是 回文串。
请你返回结果字符串。如果无法做到则返回一个 空串 。
如果两个字符串长度相同那么字符串 a 字典序比字符串 b 小可以这样定义在 a 和 b 出现不同的第一个位置上字符串 a 中的字符严格小于 b 中的对应字符。例如abcc” 字典序比 abcd 小因为不同的第一个位置是在第四个字符显然 c 比 d 小。
示例 1
输入palindrome abccba
输出aaccba
解释存在多种方法可以使 abccba 不是回文例如 zbccba, aaccba, 和 abacba 。
在所有方法中aaccba 的字典序最小。
示例 2
输入palindrome a
输出
解释不存在替换一个字符使 a 变成非回文的方法所以返回空字符串。 提示
1 palindrome.length 1000palindrome 只包含小写英文字母。
解题方法贪心
如果字符串只有一个字符那么改成什么都是回文直接返回空字符串。
如果字符串的长度为奇数那么修改正中间的字符是没有意义的修改后仍是回文串。
为了让修改后的字符串前面字符尽可能小对于一个长度不只为1的字符串 遍历字符串的前一半不遍历到字符串正中间元素或后半字符串一旦出现非a字符就将这个字符修改为a并返回 否则前半字符串(不包含正中间字符)全是a说明后半字符串也全是a将最后一个字符修改为b并返回 时间复杂度 O ( l e n ( p a l i n d r o m e ) ) O(len(palindrome)) O(len(palindrome)) 空间复杂度 O ( 1 ) O(1) O(1)。C可变字符串可直接修改原字符串并返回其他不可变字符串的编程语言返回值不计入算法空间复杂度。
AC代码
C
/** Author: LetMeFly* Date: 2025-03-05 12:55:06* LastEditors: LetMeFly.xyz* LastEditTime: 2025-03-05 12:56:14*/
class Solution {
public:string breakPalindrome(string palindrome) {if (palindrome.size() 1) {return ;}for (int i 0; i palindrome.size() / 2; i) {if (palindrome[i] ! a) {palindrome[i] a;return palindrome;}}palindrome.back() b;return palindrome;}
};Python Author: LetMeFly
Date: 2025-03-05 15:57:15
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-05 15:59:07class Solution:def breakPalindrome(self, palindrome: str) - str:if len(palindrome) 1:return s list(palindrome)for i in range(len(palindrome) // 2):if palindrome[i] ! a:s[i] areturn .join(s)s[-1] breturn .join(s)
Java
/** Author: LetMeFly* Date: 2025-03-05 16:00:14* LastEditors: LetMeFly.xyz* LastEditTime: 2025-03-05 16:02:39*/
class Solution {public String breakPalindrome(String palindrome) {if (palindrome.length() 1) {return new String();}char[] s palindrome.toCharArray();for (int i 0; i s.length / 2; i) {if (s[i] ! a) {s[i] a;return new String(s);}}s[s.length - 1] b;return new String(s);}
}Go
/** Author: LetMeFly* Date: 2025-03-05 16:05:35* LastEditors: LetMeFly.xyz* LastEditTime: 2025-03-05 16:07:53*/
package mainfunc breakPalindrome(palindrome string) string {if len(palindrome) 1 {return }for i : 0; i len(palindrome) / 2; i {if palindrome[i] ! a {return palindrome[:i] a palindrome[i 1:]}}return palindrome[:len(palindrome) - 1] b
}同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ 千篇源码题解已开源
