LeetCode-844. Backspace String Compare

LeetCode-844. Backspace String Compare

難度: easy

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

給2字串s和t，如果他們在輸入進空的文字編輯器時相同則回傳true，'#' 這個符號代表退格字元

如果在空白文字編輯器再輸入退格字元，文字還是空白

(鳥翻譯請見諒，如有錯誤請協助指出，感謝

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".

Constraints:

• 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?

解題流程

1. 先看懂題目想描述甚麼情境
2. 開始想像程式運作該經過哪些流程
3. 將經過的流程所需的判斷跟細節列出
4. 實作列出的流程

先看懂題目想描述甚麼情境

應該是描述當使用者在編輯器中依序輸入字串s或t時，過程中可能需要刪除打錯的字，所以會透過’#'(退格字元)來將上一個輸入進去的字刪掉，有可能打了多次’#’，所以連續刪掉多個字，在編輯器為空白的情況下，輸入’#’還是維持空白。

開始想像程式運作該經過哪些流程

想像中已經輸入的字會被下一個輸入的字元決定是要保留還是要移除，每次輸入的時候都要再判斷一次，但如果目前已輸入字串已經是空的情況下，下一個輸入的還是’#’，還是要保持空字串

將經過的流程所需的判斷跟細節列出

已輸入的字會被下一個輸入的字元決定是要保留還是要移除，這部分要先看看，下一個輸入的字是不是’#’

如果是的話——————————————————————————-
要判斷如果有已輸入字串，要把已輸入字串的最尾端拔掉
如果沒有則直接略過這個’#'(你在空白編輯器按退格字元，不應該加入任何字到文字編輯器)
——————————————————————————————-
如果不是直接加進已輸入的字串的最尾端

實作列出的流程

typescript

function backspaceCompare(s: string, t: string): boolean {
    if(s.length === 1 && t.length === 1) {
        return s === t
    }
    return computeString(s) === computeString(t);
};

function computeString(s): string{
    let stackString = '';
    for(let i = 0; i < s.length; i++) {
        if(s[i] !== '#') {
            stackString = stackString + s[i];
        } else if(stackString.length) {
            stackString = stackString.substring(0, stackString.length - 1)
        }
    }
    return stackString;
}

感謝閱讀，如果有錯誤或是講得不清楚的部分，再請留言指教