題目連結:
題目意譯:
給定一個包含 '(' 、')' 和小寫英文字母的字串 s。
你的任務是移除最少的括號(在任意位置的 '(' 或是 ')')使得得到的括號字串是合法的,並回傳任何一個合法的字串。
更正式地說,一個括號字串是合法的若且唯若:
如果其為空字串、只包含小寫英文字母,抑或是
其可以被寫為 AB(A 串接著 B),其中 A 和 B 為合法字串,又或是
其可以被寫為 (A),其中 A 為一合法字串。
限制:
1 ≦ s.length ≦ 10 ^ 5
s[i] 只會是 '(' 、')' 或是小寫英文字母。
範例測資:
範例 1:
輸入: s = "lee(t(c)o)de)"
輸出: "lee(t(c)o)de"
解釋: "lee(t(co)de)" 、 "lee(t(c)ode)" 也是可以被接受的。
範例 2:
輸入: s = "a)b(c)d"
輸出: "ab(c)d"
範例 3:
輸入: s = "))(("
輸出: ""
解釋: 一個空字串也是合法的。
解題思維:
基本上就是括號匹配的問題(如
這題),只是當我們遇到不平衡(也就是遇到會使字串不合法的括號)的時候,我們就先標記該括號(直接移除的話,最糟就是全部字元被移除,這個情況下會跑很久)。
然後判斷完後,掃一次字串然後把那些沒有被標記的字元通通依序丟到一個新的字串。而這個新字串將會是用盡可能少的括號移除所得到的合法字串,因此其為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。