企业官网建设流程全解析

LeetCode 破坏回文串题解

题目描述

给你一个回文串s，你最多可以修改一个字符，将其破坏成非回文串。请问你能得到的字典序最大的破坏后的字符串是什么？

示例：

输入：s = "abccba"
输出："aaccba"

输入：s = "a"
输出："b"

解题思路

方法：贪心

思路：

• 使用贪心算法来解决这个问题。
• 遍历字符串的前半部分，对于每个字符：
  • 如果字符不是 'a'，将其修改为 'a'，返回修改后的字符串。
• 如果遍历完前半部分都没有修改，说明字符串是形如 "aaaa...a" 的回文串。
• 将字符串的最后一个字符修改为 'b'，返回修改后的字符串。

复杂度分析：

• 时间复杂度：O(n)，其中 n 是字符串的长度。
• 空间复杂度：O(n)，需要额外的空间来存储结果字符串。

代码实现

方法：贪心

# 破坏回文串（贪心） def break_palindrome(palindrome_str): n = len(palindrome_str) if n == 1: return "" chars = list(palindrome_str) for i in range(n // 2): if chars[i] != 'a': chars[i] = 'a' return ''.join(chars) chars[-1] = 'b' return ''.join(chars) # 测试 def test_break_palindrome(): s = "abccba" print(break_palindrome(s)) # 输出："aaccba" s = "a" print(break_palindrome(s)) # 输出："" if __name__ == "__main__": test_break_palindrome()

测试用例

测试用例 1：基本情况

输入：s = "abccba"
输出："aaccba"

测试用例 2：单字符回文串

输入：s = "a"
输出：""

总结

破坏回文串是一个经典的贪心算法问题，它可以通过贪心算法来高效地解决。

贪心算法的核心思想是：将字符串前半部分的非 'a' 字符修改为 'a'，这样可以得到字典序最大的破坏后的字符串。

掌握贪心算法的使用方法，对于解决类似的问题非常重要。