个人做网站有什么用,做网站在哪接单,四川电大住房和城乡建设厅网站,专做衬衫的网站【LetMeFly】2697.字典序最小回文串
力扣题目链接#xff1a;https://leetcode.cn/problems/lexicographically-smallest-palindrome/
给你一个由 小写英文字母 组成的字符串 s #xff0c;你可以对其执行一些操作。在一步操作中#xff0c;你可以用其他小写英文字母 替换…【LetMeFly】2697.字典序最小回文串
力扣题目链接https://leetcode.cn/problems/lexicographically-smallest-palindrome/
给你一个由 小写英文字母 组成的字符串 s 你可以对其执行一些操作。在一步操作中你可以用其他小写英文字母 替换 s 中的一个字符。
请你执行 尽可能少的操作 使 s 变成一个 回文串 。如果执行 最少 操作次数的方案不止一种则只需选取 字典序最小 的方案。
对于两个长度相同的字符串 a 和 b 在 a 和 b 出现不同的第一个位置如果该位置上 a 中对应字母比 b 中对应字母在字母表中出现顺序更早则认为 a 的字典序比 b 的字典序要小。
返回最终的回文字符串。 示例 1
输入s egcfe
输出efcfe
解释将 egcfe 变成回文字符串的最小操作次数为 1 修改 1 次得到的字典序最小回文字符串是 efcfe只需将 g 改为 f 。示例 2
输入s abcd
输出abba
解释将 abcd 变成回文字符串的最小操作次数为 2 修改 2 次得到的字典序最小回文字符串是 abba 。示例 3
输入s seven
输出neven
解释将 seven 变成回文字符串的最小操作次数为 1 修改 1 次得到的字典序最小回文字符串是 neven 。 提示
1 s.length 1000s 仅由小写英文字母组成
方法一模拟
从第一个字符遍历到字符串的中间 如果这个字符串与其对称的字符串不同就无脑将这两个字符都变成 这两个中较小的那个。 时间复杂度 O ( l e n ( s ) ) O(len(s)) O(len(s))空间复杂度 O ( 1 ) O(1) O(1)或 O ( l e n ( s ) ) O(len(s)) O(len(s))。对于不可变字符串的编程语言可能需要额外的空间如数组来存储字符串的中间形态。
AC代码
C
class Solution {
public:string makeSmallestPalindrome(string s) {for (int i 0; i s.size() / 2; i) {if (s[i] ! s[s.size() - i - 1]) {s[i] s[s.size() - i - 1] min(s[i], s[s.size() - i - 1]);}}return s;}
};Python
class Solution:def makeSmallestPalindrome(self, s: str) - str:li list(s)for i in range(len(s) // 2):if s[i] ! s[len(s) - i - 1]:li[i] li[len(s) - i - 1] min(s[i], s[len(s) - i - 1])return .join(li)同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/134964337
