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


Longest Common Prefix in an Array of Strings

Reverse words in a given string

Print all subsequences of a string

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

Swap all occurrences of two characters to get lexicographically smallest string

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

Transform One String to Another with a Minimum Number of Operations

Check if two given strings are isomorphic to each other

Print all permutations of a given string

Check whether the given string is a palindrome