Benjamin
Benjamin

新人工程師,偶爾分享工作心得(預計?

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

確認一個字串,在形成的過程是否從空字串開始,透過在字串的任意位置插入"abc"的字串而形成。
題目原文

題目: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。

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


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

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

執行時間只要3ms,最快的解法之一

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

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

CC BY-NC-ND 4.0

Like my work?
Don't forget to support or like, so I know you are with me..

Loading...
Loading...

Comment