Check if strings are equal or not after removing backspace

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.

	package com.cb.string;

	import java.util.Stack;

	/*
	* Time complexity: O(n+m)
	* Space complexity: O(n+m)
	* */
	public class S17_BackspaceStringCompare_usingStack_n_and_n {

	private static Stack<Character> finalCharStack(String s) {
	Stack<Character> stack = new Stack<>();
	for (int i = 0; i < s.length(); i++) {
	char c = s.charAt(i);
	if (c != '#') {
	stack.push(c);
	} else if (!stack.isEmpty()) {
	stack.pop();
	}
	}
	return stack;
	}

	private static boolean backspaceCompare(String s, String t) {

	Stack<Character> st = finalCharStack(s);
	Stack<Character> tt = finalCharStack(t);

	if (st.size() != tt.size())
	return false;

	while (!st.isEmpty()) {
	if (st.pop() != tt.pop())
	return false;
	}
	return true;
	}


	public static void main(String[] args) {
	String s = "bxj##tw";
	String t = "bxj###tw";
	System.out.println(backspaceCompare(s, t));// false
	}
	}