###### tags: `Leetcode` `easy` `string` `stack` `python` `c++`

# 844. Backspace String Compare

## [題目連結:] https://leetcode.com/problems/backspace-string-compare/description/

## 題目:
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 = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

## 解題想法:
* 題目為比較兩字串:
* 其中"#"表示後退鍵，能刪除前一個字元
* 若字串已空，"#"作用後仍為空

* 直接stack判斷當前字元存入即可

## Python:

class Solution(object):
    def backspaceCompare(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        def reBuild(s):
            stack=[]
            for char in s:
                if char!='#':
                    stack.append(char)
                elif char=='#' and stack:
                    stack.pop()
            return "".join(char for char in stack)
            
        newS=reBuild(s)
        newT=reBuild(t)
        return newS==newT

## C++:

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        return reBuild(s)==reBuild(t);
    }

    vector<int> reBuild(string& s){
        vector<int> res;
        for (char val: s){
            if (val!='#')
                res.push_back(val);
            else if (val=='#' && !res.empty())
                res.pop_back();
        }
        return res;
    }
};