[leetcode]1003. Check If Word Is Valid After Substitutions

題目：1003. Check If Word Is Valid After Substitutions
提示關鍵字：堆疊(stack)、列表(list)、陣列(array)

堆疊(stack)：放入和取出的出口都是同一個的資料結構，想像成一個裝書的紙箱，只能從上方放書與取書，由於最後放入的在最上方，照順序取出的第一本會是最後一本放入的書。

列表(list)：如名稱所見，就是一個列表。可以自行新增或刪除元素並決定其插入順序，也可以支援隨機存取(更新/取得第n筆資料)。

陣列(array)：宣告初始就需要定義長度，支援隨機存取(更新/取得第n筆資料)，但是基本功能並不提供變更長度的功能，不建議在需要新增或刪除的時候使用。

第一版，最直覺的想法

「如果產生的過程是在任意位置插入abc，那麼反過來想只要不斷的移除abc直到沒有為止，再確認字串是不是被清空就知道答案了嘛！」

while (s.contains("abc")) {
    s = s.replaceAll("abc", "");
}
return s.isBlank();

很意外地，這個方法的執行時間竟然並沒有落後其他方法太多，落在倒數43%的位子。

另外從這樣的規則中可以了解，如果輸入的字串長度不是三的倍數，那麼當然不可能僅由多組abc字串組成，要在確認內容之前先透過長度篩選不可能的字串也可以，但是實際使用時效果不大，因此後續解法中會略過這個小部分。

第二版，使用堆疊

如第一版想到的，符合要求的字串應該會包含相連的abc，使用堆疊的邏輯就會變這樣：

// 從頭開始一個一個字判斷
case 'a':
    // 直接加入stack，不用判斷
    stack.add()
case 'b':
    // 取出stack最上面的元素，確認值是不是a，不是就代表不符合，是就把b加入stack
    stack.pop()
    stack.add()
case 'c':
    // 取出stack最上面的元素，確認值是不是b，不是就代表不符合，是就表示完成一組abc，繼續檢查下一個字
    stack.pop()

// 直到最後都沒判斷不符合的話再確認stack有沒有隨著檢查結束而清空，如果仍有元素就表示失敗，也就是多了單獨的a或ab的情況。例如：aabc、abca、abcab。
// 取出stack內的元素時如果發現stack已經是空的那也是不符合，即b前面沒a，c前面沒b的情況

這個寫法的效率落在前半段，或許是因為頻繁的增減堆疊的元素所以效率沒有特別好。

第三版，堆疊不能直接修改元素的值？那就找東西替代吧！

我使用列表模擬堆疊，每次都針對列表最後一個元素判斷，並增減內容的話就可以完成像堆疊一樣的邏輯。

case 'a':
    list.add(1);
case 'b':
    if (list.get(list.size() - 1) == 1)
        list.set(list.size() - 1, 2);
case 'c':
    if (list.get(list.size() - 1) == 2)
        list.remove(list.size() - 1);

多餘的說明省略，從上方可以看到換成列表主要的影響就是長度變化只發生在遇到a要新增，或是確認完一組abc之後減少，看起來比較俐落。

這個方法的執行時間擠進前四分之一，記憶體用量則是前百分之五，算是相當不錯。

關於為什麼突然開始不存字元a和b而是存數字1和2的原因，主要是實際測試之後發現比起存字元，存數字的效率和空間使用表現都會提高一點(速度不變，記憶體使用從43.3變為43.7MB)。

實際上兩者皆可，甚至因為這題的目標只要檢查abc當中的bc，也可以使用布林值true、false記錄，只是布林值可擴展性較差，如果不是abc而是更長的字串會不夠表示。

第四版，用陣列取代列表，使用固定大小的空間完全不增減元素

先建立一個長度與字串同樣的陣列，想像第三版的邏輯對上面說明過的步驟做修改：

// 用一個變數nowDepth記錄原本陣列目前長度-1的值
int newDepth = -1;
int[] array = new int[s.length()];

...

case 'a':
    // list.add(1);
    array[++nowDepth] = 1;
case 'b':
    // if (list.get(list.size() - 1) == 1)
    //     list.set(list.size() - 1, 2);
    if (array[nowDepth] == 1)
        array[nowDepth] = 2;
case 'c':
    // if (list.get(list.size() - 1) == 2)
    //     list.remove(list.size() - 1);
    if (array[nowDepth] == 1)
        nowDepth--;

遇到a和確認完一組abc之後都不再增減資料，而是使用下一個位子開始記錄或退回上一個位子。

陣列長度要和字串一樣長的原因是為避免極端的情況空間不夠用，如果字串由太多a組成那就可能需要更多的空間，為求保險就這樣用了。

這個方法是我想到的範圍中最好的解法，執行時間效率進入前百分之五，而使用空間較多是預期中的結果。

番外第一版，使用對應表記錄目標增加擴展性，但有使用限制

這個方法基於第三版，我試著額外使用map這種key->value對應的結構用來記錄目標字串abc各字元的位置，在確認的過程可以直接以字元取得map裡記錄它之前應該的狀態，而且只要把定義abc的地方換成def就可以變更比對目標，只是萬一想改成比對abbc這樣包含重複字元的字串就會無法使用。

番外第二版，參考自討論區，可說是最簡單明瞭的邏輯

依序把所有字元一個一個往堆疊裡放，直到碰到c再把堆疊最上方的兩個元素取出，依序確認是不是分別是b和a。

這個解法不算特別快，大約在前三分之一的位置，比第三版還慢一些。但是邏輯簡單易懂，理解這方法的當下覺得茅塞頓開。

番外第三版，試著解釋討論區的超快解法

這個寫法的原版相當精簡也不易理解，因此我的改作實際上是試著將程式重寫為比較好讀的版本。很可惜的是我在討論區找不到這個討論串，不知道是刪掉還是被排序演算法推到下面了，原版程式如圖：

改作之後發現和我的第四版邏輯接近，只不過他不是額外建立陣列，而是直接使用輸入字串轉換為的陣列，反正檢查過的字串剩下的空間再利用也不會造成問題；此外還以基於abc是連續字母的前提減少比對的邏輯。

前者是我完全沒想到的點子，重複利用空間是個很神奇的做法，我很佩服；後者有侷限性，如果換成非連續字母例如bac就不成立，因此雖然也有想到過但沒有實行。