AMAZON Problem Statement 1

Coding Question Asked in ONLINE ASSESSMENT (AMAZON)
Given two strings containing a special character '#' which represents a backspace, you need to print true if both the strings will be equal after processing the backspaces

Example:
    SOGB##OKSG#HMASB#
    SOOKSHG#MASA#
Output:
    True
Difficulty:
    Easy

Explanation :

• For First Line (SOGB##OKSG#HMASB#): First # removes B, second # removes G, third # removes G, fourth # removes B so SOOKSHMAS left
• For Second Line (SOOKSHG#MASA#) : First # removes G, second # removes A so SOOKSHMAS left
• As result , both the lines are equal hence output should be true.

Solution:

• This can be done in many ways

1. Using StringBuilder and String within while loop

   public static void main(String[] args){
           String s1 = "SOGB##OKSG#HMASB#";
           String s2 = "SOOKSHG#MASA#";
           StringBuilder str1 = new StringBuilder(s1);  //s1 is converted to StringBuilder
           StringBuilder str2 = new StringBuilder(s2);  //s2 is converted to StringBuilder
   
           while(s1.contains("#")){
               for(int i = 0; i < s1.length(); i++){
                   if(str1.charAt(i) == '#'){
                       str1.deleteCharAt(i);
                       str1.deleteCharAt(i-1);
                   }
                   s1 = str1.toString();            //str1 is again converted to string in order to check # is present or not
               }
           }
           while(s2.contains("#")){
               for(int i = 0; i < s2.length(); i++){
                   if(str2.charAt(i) == '#'){
                       str2.deleteCharAt(i);
                       str2.deleteCharAt(i-1);
                   }
                   s2 = str2.toString();
               }
           }
           if(s1.equals(s2)){
               System.out.println("True");
           }else{
               System.out.println("False");
           }
       }

   We use both String and StringBuilder because String contains a method charAt whereas StringBuilder contains deleteCharAt()

2. Using regex in while loop

   public static void main(String... S){
       String s1 = "SOOKSHG#MASA#";
       String s2 = "SOOKSHG#MASA#";
       
       while(s1.contains("#")
           s1 = s1.replaceAll("^#+|[^#]#","");    // ^#+ represents one or more and selects those
       while(s1.contains("#")                     // [^#]# represents # with previous character
           s2= s2.replaceAll("^#+|[^#]#","");  
       if(s1.equals(s2)){ 
           System.out.println("True"); 
       }else{ 
           System.out.println("False"); 
       }   
   }

3. Using Stack Data Structure

   public static Stack<String> backSpacedString(String str){
       //creaing temporary stack
           Stack<String> stack= new Stack<String>();
   
           String[] arr = str.split("");   //It returns array of string containing every character of the str
   
           for(int i = 0; i < arr.length; i++){
               if(arr[i].equals("#"))stack.pop();
               else stack.push(arr[i]);
           }
           return stack;
       }
   
       public static void main(String... S){
           String s1 = "SOGB##OKSG#HMASB#";
           String s2 = "SOOKSHG#MASA#";
   
           Stack<String> stack1 = backSpacedString(s1);
           Stack<String> stack2 = backSpacedString(s2);
   
           if(stack1.equals(stack2))System.out.print("True");
           else System.out.print("False");
       }