從LeetCode學演算法 - 107 String (7) / Stack (2)

1544. Make The String Great (Easy)

好久不見啦！最近筆者比較忙碌，還請多多見諒XD

寫在前面

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/leetcodeadv

「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/leetcodeall

Question

Given a string s of lower and upper case English letters.

A good string is a string which doesn’t have two adjacent characters s[i] and s[i + 1] where:

0 <= i <= s.length - 2
s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa .

To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

Example 1

1
2
3
Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".

Example 2

1
2
3
4
5
Input: s = "abBAcC"
Output: ""
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

Example 3

1
2
Input: s = "s"
Output: "s"

Constraints

1 <= s.length <= 100
s contains only lower and upper case English letters.

分析/解題

給定一個字串s，當中含有大小寫的英文字母，
一個好的字串被定義為對於 0 ≤ i ≤ s.length - 2 來說，
兩個相鄰的字元s[i]和s[i+1]不會含有相同字母但大小寫相反的狀況，
例如aA, Cc這種型式。

要讓字串變好，可以透過每次拿掉兩個相鄰且讓字串變壞的字元達到，
最終得到一個好的字串。

題目表示給定的題目一定有答案且必然是唯一的。
(空字串也是好的字串)

說起來這題的標題不禁讓人想到美國總統大選，
不過到現在恐怕已經大勢底定了就是，
這句話恐怕就要成為絕響了吧XD

扯遠了，我們來看看這題。

由於它已經保證會有唯一解，
那麼相鄰字元的移除順序理論上並不會影響結果，
所以直觀上好像可以每次掃過一遍字串，
將大小寫相鄰的相同字母移掉就解決了……嗎？

但這麼做的話，我們會不知道要掃過幾次字串才能夠將所有問題移除完，
因為比如碰到abBA 這樣子的字串，我們要將**’bB’** 移除掉，
才會在下一次發現**’aA’** 可以移除。

所以為求簡單起見，
我們可以使用一個Stack 來存放已經檢查過的部分，
每次放一個字元到Stack中，存放前將Stack最上面的那個字元，
跟準備要放的字元做比較：
兩者是相同字母且大小寫相反->將Stack中最上面的字元pop掉
兩者不需相消->放入Stack

這麼一來，我們就只會放沒有讓字串變壞的字元進到Stack，
同時每次都會拿新的字元跟前面的比對，以排除掉應該移除的部分。

那麼，怎麼算大小寫相反呢？
除了用upper/lower case相關的函式外，
在 ASCII Code 中，相同大小寫的字母的對應碼會恰巧差32。

為什麼不是26? 因為中間還有帶一些標點符號。 Python中我們可以使用ord()來對一個字元取其ASCII Code值，
而在Java中，我們可以視char為一個數字來進行加減運算，
所以直接相加減就可以了。

可能有讀者會問：
「那我記不住32這個數字怎麼辦？」

在寫的過程中，我們也可以用’a’和’A’的位置差算出來，
注意**’a’對應的值是比較大** 的呦！
所以可以將其寫成：‘a’ - ‘A’ (Java)或 ord(‘a’)- ord(‘A’) (Python)

你再問：
「那我記不住哪個在前面怎麼辦？」
呃……那你只好再加個絕對值 了！
使用Math.abs() (Java) 或 abs() (Python)就可以囉！

因此，流程大體如下：

建立一個stack名為st
從字串s當中依序取出字元c，進行迴圈：
2-1. 當st不為空，且最上面的值和c的值相差32 時，就對st進行pop
2-2. 否則表示不需消除，將c推入st中(push)
完成迴圈後，將st的所有字元連起來得到的字串即為答案

依此，寫成程式碼如下：

Java

Java的部分，由於Java的Stack固定從尾端取出，
最終使用StringBuilder進行組合完以後，toString之前記得要reverse，
不然答案就會反掉囉XD！
當然，也可以採用ArrayDeque來做，
這樣就可以從頭排列到尾而不需要反轉。
使用peek()可以幫助我們確認stack的最上面一個值是什麼，
而不會將其取出，同時因不確定大小寫誰在前面，
所以檢查時要記得取絕對值！

Python

Python這邊多加了一條判斷，但其實不影響，
只是s的長度是1或0時都可以直接回傳就是了XD

我們可以看到對於Python來說好處就是可以直接拿list當stack來使用，
同時，使用join函式可以簡單地將list組成字串。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(N)，N為字串長度。Java也可以使用CharAt(i)的型式來處理取出字元的部分，但不影響空間複雜度，因為後面還有其他要組的部分XD)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

想看看其他題目嗎？
歡迎從第零篇 找你想要的！

同時追蹤粉專以獲得更多新文章的通知：
跟著Desolve學程式

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve