---
# System prepended metadata

title: 0844. Backspace String Compare
tags: [Leetcode, FaceBook, Easy, Stack]

---

# 0844. Backspace String Compare
###### tags: `Leetcode` `Easy` `FaceBook` `Stack`
Link: https://leetcode.com/problems/backspace-string-compare/
## 思路
一开始的想法是用两个stack做 复杂度O(N) O(N)
大神解法复杂度是 **O(N) O(1)**
思路是用while回圈，从后往前检查，每次检查是否有#，有则把backspace的count+1，如果backspace的count>0，就说明当前这个字符要被删除，一直找到现在没有#，backspace的count也不大于0了，就说明当前这个字符一定会被留下来，对s做完，再对t做，这时候如果s的字符不等于t的字符就说明是false
## Code
```java=
class Solution {
    public boolean backspaceCompare(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        int i = s.length()-1;
        int j = t.length()-1;
        while(true){
            int back = 0;
            while(i>=0 && (back>0 || s.charAt(i)=='#')){
                if(s.charAt(i)=='#'){
                    back++;
                }
                else{
                    back--;
                }
                i--;
            }
            
            back = 0;
            while(j>=0 && (back>0 || t.charAt(j)=='#')){
                if(t.charAt(j)=='#'){
                    back++;
                }
                else{
                    back--;
                }
                j--;
            }
            
            if(i>=0 && j>=0 && s.charAt(i)==t.charAt(j)){
                i--;
                j--;
            }
            else{
                break;
            }
        }
        return i==-1 && j==-1;
    }
}
```