[LeetCode] 844. Backspace String Compare

題目連結

844. Backspace String Compare

問題描述

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.

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 = “#a#c”
Output: true
Explanation: Both s and t become “c”.
Example 4:

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

翻譯

• 給定兩字串分別是s、 跟t，被輸入到空的文字編輯器的這兩段字串如果是一樣
  ，則回傳true，#表示一個退格鍵。
• 請注意在空字串輸入退格鍵，這段文字仍為空白。

解題思維

從字串頭讀到字串尾的解法

1. 準備一個Stack，以迭代方式讀取兩個字串中各個字元，將其儲存到Stack
2. 當讀取到字元是退格鍵#，將目前儲存在Stack第一個字元pop
   • ‘#’不儲到Stack
3. 最後將仍儲存在Stack的字元輸出成字串，即可以比對兩串字串是否一樣
4. 請參考Java解法

從字串尾讀到字串頭的解法

1. 從字串尾開始讀取各個字元
2. 當讀取到字元是退格鍵#，累加變數
   • 變數用來決定讀取下一個字元是否要跳過
3. 變數大於0，跳過該字元
4. 最後比對去除刪除部分字元字串是否一樣
5. 請參考C++解法

解題報告

Level: Easy
Time Complexity: O(n)
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Backspace String Compare.
Memory Usage: 6.3 MB, less than 57.92% of C++ online submissions for Backspace String Compare.

程式完整解題

Java 解法

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return removeBackSpaces(s).removeBackSpaces(t);
    }
    
    private String removeBackSpaces(String str){
       Stack<Character> stack = new Stack<>();
       StringBuilder builder = new StringBuilder();
       for(char c : str.toCharArray()){
           if(c == '#') {
               if(!stack.isEmpty()) {
                   stack.pop();
               }
           } else {
               stack.push(c);
           }
       }
       
       while(!stack.isEmpty()){
           builder.append(stack.pop());
       }
       return builder.toString();
    }
}

C++ 解法

#include <string>
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        return removeBackSpaces(s).compare(removeBackSpaces(t)) == 0;
    }
private:
    string removeBackSpaces(string str) {
        string newString;
        int skip = 0;
        for(int i = str.length() - 1; i >= 0; i--) {
            if(str[i] == '#') {
                skip++;
            } else {
                if(skip > 0) {
                    skip--;
                } else {
                    newString.push_back(str[i]);
                }
            }
        }
        return newString;
    }
};