刪除字串中的所有相鄰重複項
給出由小寫字母組成的字串 S ,重複項刪除操作 會選擇兩個相鄰且相同的字母,並刪除它們。在 S 上反覆執行重複項刪除操作,直到無法繼續刪除。 |
在完成所有重複項刪除操作後返回最終的字串。答案保證唯一。
示例:
輸入:"abbaca" 輸出:"ca" 解釋: 例如,在 "abbaca" 中,我們可以刪除 "bb" 由於兩字母相鄰且相同,這是此時唯一可以執行刪除操作的重複項。之後我們得到字串 "aaca",其中又只有 "aa" 可以執行重複項刪除操作,所以最後的字串為 "ca"。
提示:
<= S.length <= 20000 S 僅由小寫英文字母組成。
解法:利用棧
解題思路: 遍歷字串,依次入棧,入棧時判斷與棧頭元素是否一致,如果一致,即這兩個元素相同相鄰,則需要將棧頭元素出棧,並且當前元素也無需入棧
解題步驟: 遍歷字串,取出棧頭字元,判斷當前字元與棧頭字元是否一致
不一致,棧頭字元進棧,當前字元進棧
一致,即棧頭字元與當前字元相同相鄰,都不需要進棧,直接進入下次遍歷即可
遍歷完成後,返回棧中字串
程式碼實現:
const removeDuplicates = function(S) { let stack = [] for(c of S) { let prev = stack.pop() if(prev !== c) { stack.push(prev) stack.push(c) } } return stack.join('') };
時間複雜度:O(n)
空間複雜度:O(n
本文地址:http://www.linuxprobe.com/adjacent-duplicates-string.html
「其他文章」
- sql server如何刪除前1000行資料
- spring boot 不連線資料庫啟動
- 刪除字串中的所有相鄰重複項
- 超全面的Linux基礎知識的梳理
- 手把手教你 Socket 通訊(TCP/IP)
- Vue Openlayer中使用select選擇要素
- 對order by的理解
- 在docker中haproxy的安裝以及mysql的負載均衡配置
- JavaScript字串中URL的檢測並轉換為連結
- 只要有熱情和方法就能學好Linux
- Highcharts 環境配置介紹
- Centos7安裝與配置OpenVPN伺服器
- ECharts 互動元件概述
- docker初體驗:docker部署wordpress部落格系統
- 如何使用evilscan 掃描網路
- docker初體驗:docker 自己定製映象
- ECharts 樣式設定介紹
- 一名合格的運維工程師的歷練之路
- Python中非常有用的三個資料科學庫
- ssl證書是由什麼組成?ssl證書是什麼?