阅读量:0
2734.执行子串操作后的字典序最小字符串【中等】
题目：
给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：
- 选择
s的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，'b' 用 'a' 替换，'a' 用 'z' 替换。
返回执行上述操作 恰好一次 后可以获得的 字典序最小 的字符串。
子字符串 是字符串中的一个连续字符序列。
现有长度相同的两个字符串 x 和 字符串 y ，在满足 x[i] != y[i] 的第一个位置 i 上，如果 x[i] 在字母表中先于 y[i] 出现，则认为字符串 x 比字符串 y 字典序更小 。
示例 1：
输入：s = "cbabc" 输出："baabc" 解释：我们选择从下标 0 开始、到下标 1 结束的子字符串执行操作。 可以证明最终得到的字符串是字典序最小的。
示例 2：
输入：s = "acbbc" 输出："abaab" 解释：我们选择从下标 1 开始、到下标 4 结束的子字符串执行操作。 可以证明最终得到的字符串是字典序最小的。
示例 3：
输入：s = "leetcode" 输出："kddsbncd" 解释：我们选择整个字符串执行操作。 可以证明最终得到的字符串是字典序最小的。
提示：
1 <= s.length <= 3 * 10**5s仅由小写英文字母组成
分析问题：
读题意，可以知道这道题就是在从前往后遍历把每个非a的字母都变成它之前的小写字母，这里可以用ASCLL码进行实现，并且只能选择一个子序列。什么意思呢？ 就是只能选择在两个a中间夹着的一个子序列，或者是一个a前面的子序列，如果前面的子序列为空字符串，那么就是a后面的子序列。
需要注意的是，这里必须要操作一次，也就是说如果s全是a的话，也必须要执行一次操作，那么当然是选最后的一个a将其变成z是字典序最小的情况。
思路很简单，总的来说就是把字符串以‘a’为标志分隔，取最前面一个不空的字符串作为我们选择的子字符串来修改。
这种思路虽然是正确的，但是复杂度太高，代码太复杂，需要处理的细节很多。所以我们可以对该代码进一步优化。
优化思路如下：
- 首先获取输入字符串
s的长度n，并初始化一个索引i为 0 。 - 通过一个
while循环，从字符串的开头开始，找到第一个不是'a'的字符的位置i。 - 如果整个字符串都是
'a'（即i == n），那么将字符串的最后一个字符改为'z'并返回。 - 然后初始化另一个索引
j = i，通过另一个while循环，从位置i开始找到第一个'a'的位置j。 - 对于从位置
i到位置j的这部分子串，将每个字符的 ASCII 值减 1 ，得到新的子串。 - 最后将原始字符串的前
i个字符、新生成的子串和位置j之后的字符拼接起来返回。
代码实现：
优化前：
class Solution: def smallestString(self, s: str) -> str: # 如果字符串中没有 'a' if s.count('a')==0: # 将字符串转换为列表以便修改元素 s,v = list(s),'' # 遍历列表，将每个字符的 ASCII 值减 1 for i in range(len(s)): s[i] = chr(ord(s[i]) - 1) # 将修改后的列表元素重新组合成字符串 for l in s: v += l else: # 计算字符串中 'a' 的个数 n = s.count('a') # 按 'a' 分割字符串并转换为列表 ls = list(s.split('a')) key = '' b = '' # 找到第一个非空的子串 for k in ls: if k!= '': key = k b = k break # 如果没有找到非空子串 if key == '': return s[:-1] + 'z' # 将非空子串转换为列表 key = list(key) # 遍历非空子串列表，将每个字符的 ASCII 值减 1 for j in range(len(key)): key[j] = chr(ord(key[j]) - 1) p = '' # 将修改后的非空子串列表元素重新组合成字符串 for l in key: p += l # 将修改后的非空子串放回原列表中 ls[ls.index(b)] = p v = '' # 重新组合处理后的列表为字符串，并在适当位置插入 'a' for j in ls: if j == '' and n > 0: v += 'a' n -= 1 else: v += j if n > 0: v += 'a' n -= 1 # 如果处理后的字符串与原始字符串不同 if v!= s: return v # 如果处理后的字符串与原始字符串相同，将最后一个字符改为 'z' 并返回 return v[:-1] + 'z'
优化后：
class Solution: def smallestString(self, s: str) -> str: n = len(s) i = 0 while i < n and s[i] =='a': i +=1 if i == n: return s[:-1] + "z" j = i while j< n and s[j] != 'a': j+=1 return s[:i] + "".join(chr(ord(c) - 1) for c in s[i:j]) + s[j:]
总结：
考点：
- 字符串的遍历和索引操作。
- 条件判断（
while循环的条件）。 - 字符的 ASCII 值操作（通过
ord和chr函数）。
收获：
- 加深了对字符串处理的理解，包括如何遍历和根据条件提取子串。
- 学会了使用
ord和chr函数来操作字符的 ASCII 值，实现对字符的修改。 - 掌握了通过多个索引和循环来处理字符串中特定部分的技巧。
- 提高了在处理复杂字符串问题时的逻辑思维和代码实现能力。
