LeetCode#1047-Remove All Adjacent Duplicates In String-刪除字元串中的所有相鄰重複項
- 2020 年 4 月 4 日
- 筆記
一、題目
給出由小寫字母組成的字元串 S，重複項刪除操作會選擇兩個相鄰且相同的字母，並刪除它們。
在 S 上反覆執行重複項刪除操作，直到無法繼續刪除。
在完成所有重複項刪除操作後返回最終的字元串。答案保證唯一。
示例：
輸入："abbaca" 輸出："ca" 解釋： 例如，在 "abbaca" 中，我們可以刪除 "bb" 由於兩字母相鄰且相同，這是此時唯一可以執行刪除操作的重複項。 之後我們得到字元串 "aaca"，其中又只有 "aa" 可以執行重複項刪除操作，所以最後的字元串為 "ca"。 提示：
- 1 <= S.length <= 20000
- S 僅由小寫英文字母組成。
二、題解
- 題解1：PHP自帶的函數
str_replace
將 aa 到 zz 的 26 種重複項放入集合中,將字元串中這些重複項替換成空字元串。
function removeDuplicates($S) { $vowels = ['aa', 'bb', 'cc', 'dd', 'ee', 'ff', 'gg', 'hh', 'ii', 'jj', 'kk', 'll', 'mm', 'nn', 'oo', 'pp', 'qq', 'rr', 'ss', 'tt', 'uu', 'vv', 'ww', 'xx', 'yy', 'zz']; while (strlen($S) >= 2) { $S = str_replace($vowels, "", $S); if ($S == str_replace($vowels, "", $S)) { break; } } return $S; } - 題解2：出隊入棧結合
首先把字元串轉化為數組，可以把這個字元串數組當做一個隊列；
設置一個棧，判斷字元串數組的隊頭元素和棧頂元素是否相等，如果不相等，就將字元串數組的隊首元素出隊，壓入棧中，
反之，則將隊首元素出隊，同時將棧頂元素彈出。
時間複雜度：O(N)，空間複雜度：O(N)。
function removeDuplicates($S) { if (strlen($S) <= 1) { return $S; } $stack = []; $arr = str_split($S); while (!empty($arr)) { if (empty($stack)) { $stack[] = array_shift($arr); } else { if (current($arr) == end($stack)) { array_shift($arr); array_pop($stack); } else { $stack[] = array_shift($arr); } } } return implode("", $stack); } 
