Check if given 2 strings are same with backspace character

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

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *