LeetCode 5483. 整理字串

目錄結構

1.題目

2.題解

---

1.題目

給你一個由大小寫英文字母組成的字串 s 。

一個整理好的字串中，兩個相鄰字元 s[i] 和 s[i + 1] 不會同時滿足下述條件：

• 0 <= i <= s.length - 2
• s[i] 是小寫字元，但 s[i + 1] 是相同的大寫字元；反之亦然 。

請你將字串整理好，每次你都可以從字串中選出滿足上述條件的 兩個相鄰 字元並刪除，直到字串整理好爲止。

請返回整理好的 字串 。題目保證在給出的約束條件下，測試樣例對應的答案是唯一的。

注意：空字串也屬於整理好的字串，儘管其中沒有任何字元。

範例：

輸入：s = "leEeetcode"
輸出："leetcode"
解釋：無論你第一次選的是 i = 1 還是 i = 2，都會使 "leEeetcode" 縮減爲 "leetcode" 。


輸入：s = "abBAcC"
輸出：""
解釋：存在多種不同情況，但所有的情況都會導致相同的結果。例如：
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""


輸入：s = "s"
輸出："s"

提示：

• 1 <= s.length <= 100
• s 只包含小寫和大寫英文字母

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/make-the-string-great
著作權歸領釦網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

2.題解

通過棧儲存，實時判斷即可。

public class Solution5483 {

    @Test
    public void test5483() {
        System.out.println(makeGood("leEeetcode"));
    }

    public String makeGood(String s) {
        Stack<Character> stack = new Stack<>();
        stack.push(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!stack.empty()) {
                if (stack.peek() + 32 == c || stack.peek() - 32 == c) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            } else {
                stack.push(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.empty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}

• 時間複雜度：
• 空間複雜度：