> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/8.data-structure/844.-backspace-string-compare.md).

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

&#x20;

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

### Solution:

**Version 1:** 借助栈来存储非‘#’的字符，当非‘#’时，入栈，当得到‘#’时判断是否需要出栈

```
class Solution {
    public boolean backspaceCompare(String s, String t) {
        return backspacing(s).equals(backspacing(t));
    }
    
    public String backspacing(String word)
    {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i< word.length(); i++)
        {
            if(word.charAt(i) != '#')
            {
                stack.push(word.charAt(i) );
            }else
            {
                if(!stack.isEmpty())
                {
                    stack.pop();
                }
            }
        }
        // 注意这里可以直接将stack转化成String
        return String.valueOf(stack);
    }
}
```

**Version 2:  O(1) space**

```
public class Solution {
    public bool BackspaceCompare(string s, string t) {
        int sback=0,tback=0;
        int i=s.Length-1,j=t.Length-1;
        char hash='#';
        
        while(i>=0 || j>=0)
        {
            //find first non # character in s string
            while(i>=0)
            {
                if(s[i]==hash)
                {
                    sback++;
                    i--;
                }
                else if(sback>0)
                {
                    sback--;
                    i--;
                }
                else
                    break;
            }
            
            //find first non # character in t string
            while(j>=0)
            {
                if(t[j]==hash)
                {
                    tback++;
                    j--;
                }
                else if (tback>0)
                {
                    tback--;
                    j--;
                }
                else
                    break;
            }
            
            if(i>=0 && j>=0 && s[i]!=t[j])
                return false;
            if((i>=0) != (j>=0))
                return false;
            
            i--;
            j--;
        }
        
        return true;
    }
}
```