Code Destine

Problem Statement

You have given two strings S and T, write a program to check if they are equal when they are types into empty text editors.

Note: # means a backspace character.

Example 

Input :- S = "ab#cde#", T = "ad#cd"
Output :- true

Input :- S = "ab##e", T = "c#d#f"
Output :- false

Solution

The Stack data structure can be used to solve this problem, following are the steps :-

1. Create the character array from the input Strings S and T.
2. Iterate through the character array of S and at each iteration, check if the character is #.
3. If yes, then pop the top element of the stack.
4. If no, then push the current element on the top of the stack.
5. Create string Stemp from the remaining elements of the stack and clear it.
6. Repeat steps 2, 3, 4 and 5 for character array of T.
7. Compare string Stemp and Ttemp, if they are equal return true otherwise return false.

Program

import java.util.Stack;

public class Main {

	public static void main(String[] args) {		
		Main main = new Main();
		boolean result = main.backspaceCompare("ab##e","c#d#f");
		System.out.print(result);										
	}  
	
	/* Solution */    
	public boolean backspaceCompare(String S, String T) {
		
        Stack<Character> stack = new Stack<>();
        char[] Sarray = S.toCharArray();
        for(int i=0; i<Sarray.length; i++){ 
            if(Sarray[i] == '#'){ 
                if(stack.size() >0){
                    stack.pop();
                }                
            }else {
                stack.push(Sarray[i]);
            }
        }
        String first = String.valueOf(stack);
        
        stack.clear();
        
        char[] Tarray = T.toCharArray();
        for(int i=0; i<Tarray.length; i++){ 
            if(Tarray[i] == '#'){ 
                if(stack.size() >0){
                    stack.pop();
                }
            }else {
                stack.push(Tarray[i]);
            }
        }
        String second = String.valueOf(stack);
        
        return first.equals(second);
    }
}

Result

false 

Similar Post

1. Valid Parentheses
2. Next Greater Element
3. Implement Stack using Queues

That’s all for Backspace String Compare in Java, If you liked it, please share your thoughts in a comments section and share it with others too.