JZX轻语：简
LeetCode 3106 - 满足距离约束且字典序最小的字符串
发表于2024年07月27日
本质上k就是最多可以操作的次数，其中由字符c1变换到字符c2需要操作的次数为min((ord(c1) - ord(c2) % 26, (ord(c1) - ord(c2)) % 26)(要么顺着变化，要么逆着)。为了得到字典序最小的结果，需要从左往右尽可能地将前面的字符翻转成a(两种操作方法中选取代价最小的方法)，如果剩余的次数不足以翻转到a，则往前翻转ASCII序更小的字符。
为什么在剩余的次数无法到达a的情况下，只能往前翻转得到ASCII序更前的字符，而不尝试往后翻转呢？因为两种操作方法都无法到达a，而往后翻转的办法中，能到达的ASCII序比原字符小的、且所需代价最小的字符就是a，既然这样无法到达a，更不用说b、c等等了。
class Solution:
def getSmallestString(self, s: str, k: int) -> str:
def distance(ch1: str, ch2: str) -> int:
""" 求解两个字符之间的最小操作次数 """
ord_ch1 = ord(ch1)
ord_ch2 = ord(ch2)
return min((ord_ch1 - ord_ch2) % 26, (ord_ch2 - ord_ch1) % 26)
ans = []
for ch in s:
dis_to_a = distance('a', ch)
if dis_to_a <= k: # 剩余的次数足够翻转到a
k -= dis_to_a
ans.append('a')
else: # 否则，只能尽可能往前找ASCII序更小的字符
ans.append(chr(ord(ch) - k))
break
ans.append(s[len(ans):]) # 将剩余的字符直接拼接到结果中
return ''.join(ans)第一次的做法，在遍历每个位置的时候都从a到z枚举一遍，在操作次数不超过剩余次数的情况下尽可能找到ASCII序最小的字符。
import string
class Solution:
def getSmallestString(self, s: str, k: int) -> str:
def distance(ch1: str, ch2: str) -> int:
ord_ch1 = ord(ch1)
ord_ch2 = ord(ch2)
return min((ord_ch1 - ord_ch2) % 26, (ord_ch2 - ord_ch1) % 26)
ans = []
for ch in s:
if k == 0:
break
for target in string.ascii_lowercase: # 从a到z枚举一遍
dis = distance(target, ch)
if dis <= k:
# 操作的次数在剩余次数内, 直接使用该字符
ans.append(target)
k -= dis
break
ans.append(s[len(ans):])
return ''.join(ans)