class Solution {
public:
string makeSmallestPalindrome(string s) {
}
};
6454. 字典序最小回文串
给你一个由 小写英文字母 组成的字符串 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 仅由小写英文字母组成原站题解
javascript 解法, 执行用时: 144 ms, 内存消耗: 49.6 MB, 提交时间: 2023-12-13 00:19:55
/**
* @param {string} s
* @return {string}
*/
var makeSmallestPalindrome = function(s) {
s = s.split('');
let left = 0, right = s.length - 1;
while (left < right) {
if (s[left] != s[right]) {
if (s[left] < s[right]) {
s[right] = s[left];
} else {
s[left] = s[right];
}
}
++left;
--right;
}
return s.join('');
};
rust 解法, 执行用时: 8 ms, 内存消耗: 2.2 MB, 提交时间: 2023-12-13 00:19:27
impl Solution {
pub fn make_smallest_palindrome(s: String) -> String {
let mut chrs: Vec<char> = s.chars().collect();
let (mut prev, mut back) = (0_usize, chrs.len() - 1);
while prev < back {
let c = std::cmp::min(chrs[prev], chrs[back]);
chrs[prev] = c;
chrs[back] = c;
prev += 1;
back -= 1;
}
let mut s: String = String::new();
for c in chrs {
s.push(c);
}
s
}
}
cpp 解法, 执行用时: 28 ms, 内存消耗: 15 MB, 提交时间: 2023-12-13 00:19:02
class Solution {
public:
string makeSmallestPalindrome(string s) {
for (int i = 0, n = s.length(); i < n / 2; i++) {
char x = s[i], y = s[n - 1 - i];
if (x > y) s[i] = y;
else s[n - 1 - i] = x;
}
return s;
}
};
golang 解法, 执行用时: 12 ms, 内存消耗: 6.8 MB, 提交时间: 2023-05-22 14:31:24
func makeSmallestPalindrome(S string) string {
s := []byte(S)
for i, n := 0, len(s); i < n/2; i++ {
x, y := s[i], s[n-1-i]
if x > y {
s[i] = y
} else {
s[n-1-i] = x
}
}
return string(s)
}
java 解法, 执行用时: 7 ms, 内存消耗: 43.3 MB, 提交时间: 2023-05-22 14:31:08
class Solution {
public String makeSmallestPalindrome(String S) {
var s = S.toCharArray();
for (int i = 0, n = s.length; i < n / 2; i++) {
char x = s[i], y = s[n - 1 - i];
if (x > y) s[i] = y;
else s[n - 1 - i] = x;
}
return new String(s);
}
}
python3 解法, 执行用时: 136 ms, 内存消耗: 16.2 MB, 提交时间: 2023-05-22 14:30:56
class Solution:
def makeSmallestPalindrome(self, s: str) -> str:
s = list(s)
for i in range(len(s) // 2):
x, y = s[i], s[-1 - i]
if x > y: s[i] = y
else: s[-1 - i] = x
return ''.join(s)