模擬特定字元處理

通常有邊走邊決定丟掉或保留的情況可以用stack來處理

Leetcode 1047. Remove All Adjacent Duplicates In String

題目：刪掉相鄰且相同的字元
輸入：s = "abbaca"
輸出："ca"
限制：

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.

解法：依順序判斷目前字元，沒跟前一個重複就放到stack保存，重複就刪掉目前跟前一個字元。

impl Solution {
    pub fn remove_duplicates(s: String) -> String {
        let mut stack = Vec::new();
        for c in s.chars() {
            if let Some(&top) = stack.last() {
                if (top==c){
                    stack.pop();
                } else {
                    stack.push(c);
                }
            } else {
                stack.push(c);
            }
        }
        stack.iter().collect()
    }
}

時間複雜度O(n)

Leetcode 394. Decode String

題目：給一字串有格式為k[encoded_string]，k為正整數代表字串重複次數。
輸入：s = "3[a]2[bc]"
輸出："aaabcbc"

限制：

• 1 <= s.length <= 30
• s consists of lowercase English letters, digits, and square brackets '[]'.
• s is guaranteed to be a valid input.
• All the integers in s are in the range [1, 300].

解法1：這題是括號匹配加上特定字元處理，需要匹配[]，且[前是數字

1. 用一個stack存所有字元，遇到]再開始組合成目標字串直到遇到[
2. 將數字字元組合變成重複次數
3. 目標字串*重複字數
4. 組完後轉成字元存進stack
5. 跑完迴圈，回傳最後結果

impl Solution {
    pub fn decode_string(s: String) -> String {

        let mut stack = Vec::new();
        let mut current_string = String::new();
        let mut digit_string = String::new();
        for c in s.chars() {
            if (c!=']'){
                stack.push(c);
            } else {
                loop {
                    let Some(element) = stack.pop() else { break };
                    if (element=='['){
                        break
                    } else {
                        current_string.insert(0,element);
                    }
                }
                loop {
                    let Some(digit) = stack.pop() else { break };
                    if (digit.is_ascii_digit()){
                        digit_string.insert(0,digit);
                    } else {
                        stack.push(digit);
                        break
                    }
                }
                current_string = current_string.repeat(digit_string.parse().unwrap());
                for c in  current_string.chars() {
                    stack.push(c);
                }
                current_string = String::new();
                digit_string = String::new();
            }
        }

        stack.iter().collect()
    }
}

時間複雜度：O((maxk^countk)*n)

1. 每次遇到]都需要先pop字元直到遇到[2
2. 組成字串後再轉成字元push回到stack
3. 最壞情形就是遇到10[a20[bc30[d]]]，countk=3，maxk=30
4. 我們可以用解法2避免上述情形。

解法2：

1. 分別記錄目前出現的數字和字串
2. 遇到[分別把數字和字串存到兩個stack中
3. 遇到]就執行decod，從stack pop出重複次數k和要加入的字串add_string組成add_string+current_string*k

impl Solution {
    pub fn decode_string(s: String) -> String {
        let mut d_stack=Vec::new();
        let mut s_stack=Vec::new();
        let mut digit =0;
        let mut current_string = String::new();

        for c in s.chars() {
            if(c.is_digit(10)){
                digit = digit*10+c.to_digit(10).unwrap();
                
            } else if (c=='['){
                d_stack.push(digit);
                s_stack.push(current_string.clone());
                digit = 0;
                current_string.clear();
            } else if (c==']'){
                let Some(repeat)=d_stack.pop() else { todo!() };
                let Some(add_string)=s_stack.pop() else { todo!() };
                current_string=current_string.repeat(repeat as usize);
                current_string.insert_str(0,&add_string);
            } else {
                current_string.insert(current_string.len(),c);
            }
        }
        current_string
    }
}

時間複雜度:O(maxk*n)，maxk為重複 k次時所花時間

復原動作

Leetcode 844. Backspace String Compare

題目：判斷兩字串遇到#刪除前一個字元後是否相等
輸入： s = "ab#c", t = "ad#c"
輸出：true

解法：用兩個stack依序將兩字串的字元存入，我們可以#當作是復原鍵，當輸入字元如果錯了就輸入#拿掉上次存的字元。

impl Solution {
    pub fn backspace_compare(s: String, t: String) -> bool {
        
        let mut s_stack = Vec::new();
        let mut t_stack = Vec::new();

        for c in s.chars(){
            if c=='#' {
                s_stack.pop();
            } else {
                s_stack.push(c);
            }
        }

        for c in t.chars(){
            if c=='#' {
                t_stack.pop();
            } else {
                t_stack.push(c);
            }
        }
        s_stack==t_stack
    }
}

時間複雜度:O(n)

undo & redo

用兩個stack分別記錄undo和redo動作，undo時把undo stack pop的值push到redo stack，如果後悔需要redo時只要，依序將redo stack pop就可以拿到對應的值。

Day9 總結

1. stack字元處理