雜事、解題紀錄

weekly contest 451。
感覺有點像是為 Q4 做鋪陳。

題目

https://leetcode.com/problems/resulting-string-after-adjacent-removals/description/

解法

循環字母表中的 26 字母對應到 [0, 25] 中的整數。
任意兩個字母絕對差為 1 或是 25 則稱為連續。
例如：’a’ 連續 ‘b’，然後 ‘a’ 和 ‘z’ 也連續。

只要字串中存在相鄰的連續字元，則不斷消除最左方的相鄰對。
這種操作令我聯想到經典的消除括號，可用堆疊模擬。
相似題 20. Valid Parentheses。

判斷 ‘(‘ 與 ‘)’ 改成判斷連續即可。

時間複雜度 O(N)。
空間複雜度 O(N)。

def is_consecutive(x, y):
    diff = abs(ord(x) - ord(y))
    return diff == 1 or diff == 25


class Solution:
    def resultingString(self, s: str) -> str:
        st = []
        for c in s:
            if st and is_consecutive(c, st[-1]):
                st.pop()
            else:
                st.append(c)

        return "".join(st)