Problem Statement:
You are given 2 strings, and there is a special character “#” that represents a backspace. When you encounter “#”, you have to delete the previous character.
You need to check if the given 2 strings are same.
Example
Input: s = “ab#c”, t = “ad#c”
Output: True
after removing the backspace, both strings will become “ac”.
Solution
We will be using stacks for the solution.
We start inserting the characters pne by one into the stack.
When we encounter “#” we pop one character from the stack and then compare if both the strings are same or not.
Solution in C++
#include <algorithm>
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <queue>
#include <list>
using namespace std;
bool check_if_2_strings_are_same(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;
}
int main()
{
string s = "ab#c";
string t = "ad#c";
if(check_if_2_strings_are_same(s, t))
{
cout<<"Two strings are same"<<endl;
} else {
cout<<"Two strings are NOT same"<<endl;
}
return 0;
}
Output:
Two strings are same