一魚多吃 用stack來解 Backspace String Compare_Leetcode #844

Stefen Tan on Unsplash

這題的題目在這裡:

題目敘述

題目會給定兩個字串s,t，把裡面的井字號#視為鍵盤上的backspace，往前(往左方)吃掉最靠近的字元。

請位最後全部依照規則處理完以後，s,t剩下的字串內容兩者是否相等?

例如:
s = "ab#c", t = "ad#c"

說明:
相等，s, t 依照規則操作完，最後都只剩下"ac"。

測試範例

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

約束條件

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#' characters.

Follow up: Can you solve it in O(n) time and O(1) space?

演算法

基本上這一題和前一個系列題高度相似，換湯不換藥，核心觀念都是在考backspace往前吃字元的操作和對應的stack行為模擬。

從左到右，依序掃描每個字元。

如果遇到普通字元，直接推入stack。

如果遇到井字號#，相當於我們鍵盤上的backspace 往前吃字元的功能，從stack pop出頂端的元素。

最後，留在stack內部的字元，串接在一起轉成字串，字串s, 字串t兩兩比較是否相等就是答案囉!

程式碼

class Solution:
　def backspaceCompare(self, S: str, T: str) -> bool:
　　
　　stack_s, stack_t = [], []
　　
　　# --------------------------------------
　　def final_string( stk, string ):
　　　
　　　for char in string:
　　　　
　　　　if char != '#':
					# push new character into stack
　　　　　stk.append( char )
　　　　　
　　　　elif stk:
　　　　　# pop last charachter from stack, as a result of backspace operation
　　　　　stk.pop() 
　　　　　
　　　
　　　return ''.join(stk)
　　
　　# --------------------------------------
　　
　　return final_string( stack_s, S ) == final_string( stack_t, T )
　　
　　

複雜度分析

時間複雜度: O( m+n )
從頭到尾，每個字元檢查過一遍。

空間複雜度: O( m+n )
需要兩個stack，stack耗用空間最多和輸入字串長度一樣長。

關鍵知識點

在於理解並且活用stack 先進後出FILO的特質，來實作#井字號和普通字元的配對。

記得回去複習 合法括號配對、最長合法括號配對字串長度 、移除星號 這幾題，主要的原理是相通的。

Reference:

[1] Python/JS/Java/C++ O( n ) sol by stack. [w/ Comment] - Backspace String Compare - LeetCode