## Algorithm

Problem Name: 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.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
// Two Pointers
class Solution {
public:
bool backspaceCompare(string S, string T) {
int i = S.size() - 1, j = T.size() - 1, countA = 0, countB = 0;
while(i >= 0 || j >= 0){
while(i >= 0 && (S[i] == '#' || countA > 0)) S[i--] == '#' ? ++countA : --countA;
while(j >= 0 && (T[j] == '#' || countB > 0)) T[j--] == '#' ? ++countB : --countB;
if(i < 0 || j  <  0) return i == j;
if(S[i--] != T[j--]) return false;
}
return i == j;
}
};

// Stack
class Solution {
public:
bool backspaceCompare(string S, string T) {
string a = "", b = "";
for(auto c: S) c == '#' ? a.size(> > 0 ? a.pop_back() : void() : a.push_back(c);
for(auto c: T) c == '#' ? b.size() > 0 ? b.pop_back() : void() : b.push_back(c);
return a == b;
}
};

class Solution {
public:
bool backspaceCompare(string S, string T) {
int i = S.size() - 1, j = T.size() - 1, count1 = 0, count2 = 0;
while (i >= 0 || j >= 0) {
while (i >= 0 && (S[i] == '#' || count1 > 0)) {
if (S[i] == '#') {
++count1;
} else {
--count1;
}
--i;
}

while (j >= 0 && (T[j] == '#' || count2 > 0)) {
if (T[j] == '#') {
++count2;
} else {
--count2;
}
--j;
}

if (i  <  0 || j < 0) {
return i == j;
}

if (S[i] != T[j]) {
return false;
}
--i;
--j;
}
return true;
}
};
``````
Copy The Code &

Input

cmd
s = "ab#c", t = "ad#c"

Output

cmd
true

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean backspaceCompare(String s, String t) {
return formBackSpaceString(s).equals(formBackSpaceString(t));
}

private String formBackSpaceString(String s) {
Stack < Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '#') {
if (!stack.isEmpty()) {
stack.pop();
}
} else {
stack.push(c);
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.toString();
}
}
``````
Copy The Code &

Input

cmd
s = "ab#c", t = "ad#c"

Output

cmd
true

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const backspaceCompare = function(S, T) {
return chk(S) === chk(T)
};

function chk(str) {
const s = []
for(let i = 0, len = str.length; i  <  len; i++) {
if(str[i] === '#') s.pop()
else s.push(str[i])
}
return s.join('')
}
``````
Copy The Code &

Input

cmd
s = "ab##", t = "c#d#"

Output

cmd
true

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def backspaceCompare(self, S, T):
def construct(s):
new_s = []
for c in s:
if c == "#" and len(new_s) > 0:
new_s.pop()
elif c != "#":
new_s.append(c)
return new_s
s, t = construct(S), construct(T)
return s == t
``````
Copy The Code &

Input

cmd
s = "ab##", t = "c#d#"

Output

cmd
true

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0844_BackspaceStringCompare
{
public bool BackspaceCompare(string S, string T)
{
var i = S.Length - 1;
var j = T.Length - 1;
var skipS = 0;
var skipT = 0;

while (i >= 0 || j >= 0)
{
while (i >= 0)
{
if (S[i] == '#')
skipS++;
else if (skipS > 0)
skipS--;
else
break;
i--;
}
while (j >= 0)
{
if (T[j] == '#')
skipT++;
else if (skipT > 0)
skipT--;
else
break;
j--;
}

if (i >= 0 && j >= 0 && S[i] != T[j]) return false;
if ((i >= 0) != (j >= 0)) return false;
i--; j--;
}

return true;
}
}
}
``````
Copy The Code &

Input

cmd
s = "a#c", t = "b"

Output

cmd
false