Algorithm
Problem Name: 844. Backspace String Compare
Problem Link: https://leetcode.com/problems/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 <= 200sandtonly 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;
}
};
Input
s = "ab#c", t = "ad#c"
Output
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();
}
}
Input
s = "ab#c", t = "ad#c"
Output
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('')
}
Input
s = "ab##", t = "c#d#"
Output
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
Input
s = "ab##", t = "c#d#"
Output
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;
}
}
}
Input
s = "a#c", t = "b"
Output
false