LeetCode Solution: Backspace String Compare Problem

In this article, we will be implementing the Backspace String Compare Problem.

Let's start by understanding the problem statement.

Given two strings S and T, return if they are equal when both are typed into empty text editors, where the character # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:

In the example below, we have two backspace characters in the string, and two characters, hence the strings are evaluated as empty.

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Stepwise Algorithm for Problem:

1. For a string, find the index of the character '#' in it.

2. Replace the character just before (preceeding) the above found '#' with a '#'.

3. If a '#' if preceded by another '#', then keep moving towards the starting of the string till a character other than '#' appears and then replace it with '#' as in the above step.

4. If while moving towards the start, if we reach the start fo the string, then terminate this process of finding a character other than '#' as in the above step.

5. Once this is done for the entire string, all the characters to be removed will have got converted to the '#' character.

6. Now, Initalize an Arraylist of Characters and store all the characters from the above modified string, that are other than '#' in the sequentail manner from start till the end of the string.

7. This will give us an array list of characters, with each element as a character of the output string.

8. Repeat all these steps: 1 to 7 for the 2nd string as well.

9. Now, after step 8, we will be having 2 ArrayLists, with the elements as the output characters of the two modified strings.

10. Now compare each element of the 1st ArrayList with the 2nd ArrayList.

11. If all the characters match for each of the index value, print "true"

12. Else, print "false"

Code:

class Solution {
    public boolean backspaceCompare(String S, String T) {
        
        //Finding the length of the two strings to be compared
        int l1 =S.length();
        int l2 =T.length();
        int i=0,j=0;

        //Initializing a StringBuilder to manipulate the String S.
        StringBuilder myName = new StringBuilder(S);

        //Initializing a List of Characters for the String S.        
        List<Character> z = new ArrayList<>();
    
        while(i!=l1)
        {
            if(S.charAt(i)=='#')
            {
                for(j=i-1;j>=0 && myName.charAt(j)=='#';j--)
                {
                    
                }
                if(j>=0)
                {
                    System.out.println(j);
                    myName.setCharAt(j, '#');
                }
            }
            i++;
        }
        System.out.println(myName);
        
        // String m="";
        // StringBuilder n1 = new StringBuilder(m);
        
        i = 0; j = 0;
        while(i!=l1)
        {
            if(myName.charAt(i)!='#')
            {
             //   n1.setCharAt(j++,myName.charAt(i));
                z.add(myName.charAt(i));
            }
            i++;
        }
        // n1.setCharAt(j,'\0');
        // System.out.println("OP " + n1);
               
        i = 0; j = 0;

        //Initializing the 2nd StringBuilder to manipulate the String T.
        StringBuilder myName1 = new StringBuilder(T);

        //Initializing a List of Characters for the String T.        
        List<Character> z1 = new ArrayList<>();

        while(i!=l2)
        {
            if(T.charAt(i)=='#')
            {
                for(j=i-1;j>=0 && myName1.charAt(j)=='#';j--)
                {
                    
                }
                if(j>=0)
                {
                     System.out.println(j);
                    myName1.setCharAt(j, '#');
                }
            }         
            i++;
        }
        
        
        System.out.println(myName1);
        
        // String m="";
        // StringBuilder n1 = new StringBuilder(m);
        
        
        i=0;j=0;
        while(i!=l2)
        {
            if(myName1.charAt(i)!='#')
            {
             //   n1.setCharAt(j++,myName.charAt(i));
                z1.add(myName1.charAt(i));
            }
            i++;
        }
        
        int k = z.size();
        int k1 = z1.size();
        

          //If the lenght of the two ArrayLists are not equal, then the two strings formed by them cannot be same and hence we can conclude that it is not possible and hence output false.  
         if(k!=k1)
            return false;
        
        j=0;
        
        //If each character of the first ArrayList matches with that of the 2nd for all the index positions, output true. Else, even if one character does not match, output false.     
        while(j!=k)
        {
            if(z.get(j)!=z1.get(j))
            {
                return false;
            }
            j++;
        }
            
//         for (Character zz : z) {
//     System.out.println(zz);
// }    
        return true;
    }
}

Incase of any confusion regarding the above solution, you can reach out to us over the email or can mention the query in the comments section down below.

Will answer them in the best possible way.

Thanks for reading!

We hope that this post might have helped you to get your logic even stronger and implement the code as well.

Happy Learning : )