- 博客主頁：誓則盟約
- 系列專欄：IT競賽 專欄
- 關注博主，后期持續更新系列文章
- 如果有錯誤感謝請大家批評指出，及時修改
- 感謝大家點贊👍收藏?評論??
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 值減 1for i in range(len(s)):s[i] = chr(ord(s[i]) - 1) # 將修改后的列表元素重新組合成字符串for l in s: v += lelse:# 計算字符串中 'a' 的個數n = s.count('a')# 按 'a' 分割字符串并轉換為列表ls = list(s.split('a'))key = ''b = ''# 找到第一個非空的子串for k in ls:if k!= '':key = kb = kbreak# 如果沒有找到非空子串if key == '': return s[:-1] + 'z'# 將非空子串轉換為列表key = list(key)# 遍歷非空子串列表，將每個字符的 ASCII 值減 1for j in range(len(key)):key[j] = chr(ord(key[j]) - 1)p = ''# 將修改后的非空子串列表元素重新組合成字符串for l in key: p += l# 將修改后的非空子串放回原列表中ls[ls.index(b)] = pv = ''# 重新組合處理后的列表為字符串，并在適當位置插入 'a'for j in ls:if j == '' and n > 0:v += 'a'n -= 1else: v += jif 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 = 0while i < n and s[i] =='a':i +=1if i == n:return s[:-1] + "z"j = iwhile j< n and s[j] != 'a':j+=1return s[:i] + "".join(chr(ord(c) - 1) for c in s[i:j]) + s[j:]
??總結：
考點：
- 字符串的遍歷和索引操作。
- 條件判斷（
while?循環的條件）。 - 字符的 ASCII 值操作（通過?
ord?和?chr?函數）。
收獲：
- 加深了對字符串處理的理解，包括如何遍歷和根據條件提取子串。
- 學會了使用?
ord?和?chr?函數來操作字符的 ASCII 值，實現對字符的修改。 - 掌握了通過多個索引和循環來處理字符串中特定部分的技巧。
- 提高了在處理復雜字符串問題時的邏輯思維和代碼實現能力。
