Check if two strings are equal or not after processing backspace

Posted by N.K. Chauhan on Mar 31, 2024

Given two strings, s1 and s2, containing regular characters as well as some "backspaces," represented by a "#" character.

The task is to check if the two strings are equal or not after processing the backspace characters.

Input: s = "ab#c", t = "ad#c" Output: true

Input: s = "ab##", t = "c#d#" Output: true

Input: s = "bxj##tw", t = "bxj###tw" Output: false


Solutions

Method 1: Using Stack

This problem can be solved using a stack.

The idea is to traverse each string from left to right and check for the current character; if the current character is a "#" and the stack is not empty, pop an element; otherwise, push the current character into the stack.

Once two stacks are available for each string, check if these two stacks have the same characters and return true or false accordingly.

Complexity

The time complexity of this solution is O(n+m) and space complexity is O(n+m).

Related


Print all subsequences of a string

Reverse words in a given string

Check if two given strings are isomorphic to each other

Power Set: Print all non-empty subsequences of a string

Transform One String to Another with a Minimum Number of Operations

Find all substrings of a string in "O (n^2)" time

Swap all occurrences of two characters to get lexicographically smallest string

Print all permutations of a given string

Longest Common Prefix in an Array of Strings

Check whether the given string is a palindrome