問題描述 📋

子串操作后的字典序最小字符串

給定一個僅包含小寫字母的字符串，你可以執行如下操作任意次：

1. 選擇某個子串，將其中的每個字符都替換成其前一個字母（比如 ‘b’ 變成 ‘a’，‘c’ 變成 ‘b’，以此類推，‘a’ 變成 ‘z’）。

目標是通過最少的操作使得字符串變得字典序最小。🔠

解題思路 💡

為了將字符串變得字典序最小，我們可以遵循以下步驟：

1. 尋找第一個非 ‘a’ 的字符：從左到右掃描字符串，找到第一個非 ‘a’ 的字符，并將其減一。這樣操作可以保證盡可能早地對字符串進行優化，使其字典序最小。🕵??♂?
2. 中斷操作：在減一操作后，如果再次遇到 ‘a’，我們可以中斷操作，因為繼續操作下去可能會使字符串的字典序變大。🚫
3. 特殊情況處理：如果整個字符串都是 ‘a’，我們可以將最后一個字符變成 ‘z’，使得結果字典序最小。🔚

為什么這樣做？🤔

• 盡早優化：通過盡早找到第一個非 ‘a’ 的字符并減一，可以確保字符串從最左邊開始就變得更小，這樣能最大程度上優化整個字符串的字典序。
• 避免過度修改：如果在修改一個非 ‘a’ 的字符后繼續修改其他字符，可能會導致字符串整體字典序變大。因此，在遇到 ‘a’ 后立即中斷修改，以確保修改效果最佳。
• 處理全 ‘a’ 字符串：對于全是 ‘a’ 的字符串，將最后一個字符變成 ‘z’ 可以使其變得字典序最小，這是一個邊界情況的處理。

代碼實現 💻

import scala.util.control.Breaks._object Solution {def smallestString(s: String): String = {val chars = s.toCharArrayvar changed = falsebreakable {for (i <- chars.indices) {if (chars(i) != 'a') {chars(i) = (chars(i) - 1).toCharchanged = true} else if (changed) {break()}}}// If no character was changed, change the last character to 'z'if (!changed) {chars(s.length - 1) = 'z'}new String(chars)}
}

代碼分析 🔍

1. 字符數組轉換：將字符串轉換為字符數組，以便于直接修改。🔄
2. 標志位 changed：用于記錄是否進行了字符減一操作。📌
3. 循環遍歷和中斷：使用 breakable 和 break 控制循環，確保在第一次遇到非 ‘a’ 字符并進行減一操作后，遇到 ‘a’ 時中斷操作。🛑
4. 特殊情況處理：如果未進行任何字符修改操作，則將最后一個字符改為 ‘z’。📝

時空復雜度分析 ?💾

• 時間復雜度：O(n)，其中 n 是字符串的長度。因為在最壞情況下，我們需要遍歷整個字符串一次。??
• 空間復雜度：O(n)，用于存儲字符數組。📂

通過這種方法，我們能夠高效地解決問題，并確保字符串在經過最少的操作后，字典序最小。👍

#字符串操作 #字典序 #算法 #LeetCode解題 #Scala #編程技巧

---

希望這篇博客能夠幫助你理解如何通過標志位和中斷操作來高效地解決這個問題，進一步掌握字符串的操作技巧。歡迎在評論區分享你的看法和疑問！😊📘💬