Backspace String Compare

It is a Saturday morning in the Twin Cities of Minneapolis and St. Paul. As we have been doing for a few months, my wife and I drove to the Costco store in Minneapolis, met with our son and went grocery shopping. Today we were not able to find Three Berry Blend bags. We got separate bags of strawberries and blueberries. Our son will stop later today at the Costco in Eagan. MN and will see if he is able to find a couple bags of mixed berries and a box of pens that we forgot while in Minneapolis.

This week I watched the Association for Computing Machinery (ACM) webinar “Lessons from COVID-19: Efficiency vs. Resilience” by Moshe Y. Vardi. It seems that the webinar is only accessible if you are an ACM member, which I am. I enjoyed the point he made of efficiency versus resilience not only at the software but also at the political level. At no point he mentioned politicians or political parties. In my opinion, it is a very good one-hour webinar worth your time.

I also enjoyed the article “Microsoft CEO Satya Nadella calls for a ‘referendum on capitalism’” by Grace Dean. As you know Satya Nadella is the CEO of Microsoft. In the article he calls for changes in democracy to have companies not only make money for their stock holders but to also to benefit society. For years I have been promoting the idea that in the USA we need two changes: Capitalism 2.0 and Democracy 2.0. It will be hard for such companies to accept changes because they want to maximize profits for their stock holders as much as possible in order for their C-level staff to receive large salaries, bonus and stock options. Thinking about the tax liability paid by large corporations, which is quite a fraction of what they should be paying, it makes me believe that Satya Nadella’s comments are a great start in the right direction!!!

Enough chit chat, now let’s get to the main subject of this post.

I have been working on and off on a couple LeetCode problems. I have solutions for both, but would like to achieve higher efficiency and produce more elegant solutions on both problems. In this post we will touch on LeetCode problem 844 Backspace String Compare.

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

Note that after backspacing an empty text, the text will continue empty.

Note:

1 <= S.length <= 200
1 <= T.length <= 200
S and T only contain lowercase letters and '#' characters.

Follow up:

Can you solve it in O(N) time and O(1) space?

The problem is easy to describe. Given two strings which may include one or more delete characters represented by the ‘#’, determine if the strings are equal or not. If it sounds interesting, visit LeetCode, read the requirements and the examples, and develop a solution. If you get stuck, then start reading about a solution (such as the one discussed in this post). You should stop reading as soon as you get enough inspiration to continue working on your own approach. This is the best approach to follow. It is equivalent to seeking out to a coworker when you encounter a problem.

We will solve the problem using the Java programming language. I used the VSCode IDE and developed the code on a Windows 10 machine. The selection of OS and IDE should be irrelevant.

class Solution {
    public boolean backspaceCompare(String S, String T) {
        
    }
}

As you can see we are tasked with the development of the specified function. Both strings are provided by LeetCode. Since I am going to use my computer system to tackle the problem, I had to develop a test scaffolding to drive the solution.

ab#c
ad#c
main <<< S ==>ab#c<==
main <<< T ==>ad#c<==
main <<< backspaceCompare0: true
main <<<  backspaceCompare: true
main <<< backspaceCompare1: true


ab##
c#d#
main <<< S ==>ab##<==
main <<< T ==>c#d#<==
main <<< backspaceCompare0: true
main <<<  backspaceCompare: true
main <<< backspaceCompare1: true


a##c
#a#c
main <<< S ==>a##c<==
main <<< T ==>#a#c<==
main <<< backspaceCompare0: true
main <<<  backspaceCompare: true
main <<< backspaceCompare1: true


a#c
b
main <<< S ==>a#c<==
main <<< T ==>b<==
main <<< backspaceCompare0: false
main <<<  backspaceCompare: false
main <<< backspaceCompare1: false


ab#cd
ab#cd
main <<< S ==>ab#cd<==
main <<< T ==>ab#cd<==
main <<< backspaceCompare0: true
main <<<  backspaceCompare: true
main <<< backspaceCompare1: true



main <<< S ==><==
main <<< T ==><==
main <<< backspaceCompare0: true
main <<<  backspaceCompare: true
main <<< backspaceCompare1: true


a

main <<< S ==>a<==
main <<< T ==><==
main <<< backspaceCompare0: false
main <<<  backspaceCompare: false
main <<< backspaceCompare1: false


b
main <<< S ==><==
main <<< T ==>b<==
main <<< backspaceCompare0: false
main <<<  backspaceCompare: false
main <<< backspaceCompare1: false


xywrrmp
xywrrmu#p
main <<< S ==>xywrrmp<==
main <<< T ==>xywrrmu#p<==
main <<< backspaceCompare0: true
main <<<  backspaceCompare: true
main <<< backspaceCompare1: true


bxj##
bxo#j##
main <<<      01234
main <<< S ==>bxj##<==
main <<< T ==>bxo#j##<==
main <<<      0123456
main <<< backspaceCompare0: true
main <<<  backspaceCompare: true
main <<< backspaceCompare1: true


bxj##tw
bxo#j##tw
main <<<      0123456
main <<< S ==>bxj##tw<==
main <<< T ==>bxo#j##tw<==
main <<<      012345678
main <<< backspaceCompare0: true
main <<<  backspaceCompare: true
main <<< backspaceCompare1: true

The first examples came from LeetCode. The rest are a combination of the ones that I produced or the ones form LeetCode when my code failed. The original passes worked without problems. Attempting to get a solution in O(n) time and O(1) space was a different story. I decided to generate this post without having completed the follow up. I will update the code in my GitHub repository (https://github.com/JohnCanessa/BackspaceStringCompare) if and when I get such code working.

    /**
     * Test scaffolding
     */
    public static void main(String[] args) {

        // **** open scanner ****
        Scanner sc = new Scanner(System.in);

        // **** read S ****
        String S = sc.nextLine().trim();

        // **** read T ****
        String T = sc.nextLine().trim();

        // *** close scanner ****
        sc.close();

        // ???? ????
        System.out.print("main <<<      ");
        for (int i = 0; i < S.length(); i++)
            System.out.print("" + i);
        System.out.println();

        System.out.println("main <<< S ==>" + S + "<==");
        System.out.println("main <<< T ==>" + T + "<==");

        System.out.print("main <<<      ");
        for (int i = 0; i < T.length(); i++)
            System.out.print("" + i);
        System.out.println();

        // **** process and display result ****
        System.out.println("main <<< backspaceCompare0: " + backspaceCompare0(S, T));

        // **** process and display result ****
        System.out.println("main <<< backspaceCompare1: " + backspaceCompare1(S, T));

        // **** process and display result ****
        System.out.println("main <<<  backspaceCompare: " + backspaceCompare(S, T));
    }

The test scaffolding opens the scanner and reads the two input strings. The scanner is no longer needed so we go ahead and close it. Both strings are displayed with a string of digits. I did that to be able to easily track operations on the strings with indices.

We attempt three different solutions. The last one is quite efficient according to the results returned by LeetCode.

    /**
     * Process using stacks.
     * Execution O(2 * n)
     * Runtime: 2 ms, faster than 42.83% of Java online submissions.
     * Memory Usage: 37.4 MB, less than 9.73% of Java online submissions.
     */
    static boolean backspaceCompare0(String S, String T) {

        // **** initiatization ****
        Stack<Character> sStack = new Stack<Character>();
        Stack<Character> tStack = new Stack<Character>();

        // **** process S using a stack ****
        for (char ch : S.toCharArray()) {
            if (ch != '#')
                sStack.push(ch);
            else if (!sStack.isEmpty())
                sStack.pop();
        }

        // **** process T using a stack ****
        for (char ch : T.toCharArray()) {
            if (ch != '#') 
                tStack.push(ch);
            else if (!tStack.isEmpty())
                tStack.pop();
        }

        // **** compare contents of stacks ****
        return sStack.equals(tStack);
    }

The idea is to mimic the operations using a stack for each string. After processing the strings we check the contents of the arrays. If they match the strings match.

On each stack we push into characters as we read them from a string. When we detect a ‘#’ (delete character) we check if the stack is not empty and then pop (delete) the previous character.

    /**
     * Execution O(n)
     * Time Limit Exceeded!!!
     */
    static boolean backspaceCompare1(String S, String T) {

        // **** perform sanity checks ****
        if (S == null && T == null)
            return true;
        else if (S == null || T == null)
            return false;
        else if (S.length() == 0 && T.length() == 0)
            return true;
        else if (S.length() == 0 || T.length() == 0)
            return false;

        // **** initialization ****
        int s       = S.length() - 1;
        int t       = T.length() - 1;
        int delete  = 0;

        // **** traverse the strings backwards ****
        for ( ; s >= 0 || t >= 0; ) {

            // **** count the '#' characters (if any) ****
            for (delete = 0; s >= 0 && S.charAt(s) == '#'; delete++, s--);

            // **** delete associated characters (if needed) ****
            for ( ; delete > 0 && s >= 0; s--, delete--) {
                if (S.charAt(s) == '#') {
                    delete++; s--;
                }
            }

            // **** count the '#' characters (if any) ****
            for (delete = 0; t >= 0 && T.charAt(t) == '#'; delete++, t--);

            // **** delete associated characters (if needed) ****
            for ( ; delete > 0 && t >= 0; t--, delete--) {
                if (T.charAt(t) == '#') {
                    delete++; t--;
                }
            }

            // **** delete matching characters ****
            while (s >= 0 && t >= 0 && S.charAt(s) == T.charAt(t) && S.charAt(s) != '#') {
                s--; t--;
            }

            // **** check if done ****
            if (s >= 0 && t >= 0 && 
                S.charAt(s) != T.charAt(t) && 
                S.charAt(s) != '#' && T.charAt(t) != '#')
                return false;
        }

        // **** ****
        return (s == t);
    }

This code works with the sample code. When submitted to LeetCode it times out. As you can see it is quite in efficient.

The thing to note is that it seems that the proper approach is to traverse the strings backwards. This should allow us to avoid using additional space. Since the code is too slow, please take a look and see if you can come up with changes to speed it up. Perhaps a complete new and different approach is needed. One way or the other, if you come up with an acceptable solution for the follow up, please let me know.

    /**
     * Process using strings.
     * Execution O(2 * n)
     * Runtime: 0 ms, faster than 100.00% of Java online submissions.
     * Memory Usage: 37.2 MB, less than 9.86% of Java online submissions.
     */
    static boolean backspaceCompare(String S, String T) {
        
        // **** sanity check(s) ****
        if (S.equals(T))
            return true;

        // **** compare strings ****
        return processStr(S).equals(processStr(T));
    }

This is part of my solution which I submitted to LeetCode. The idea is to perform a sanity check and then process the two strings in a different function and checking if the results match or not.

    /**
     * Process backspace(s) in a string.
     * Using strings.
     * Execution O(n)
     */
    static String processStr(String str) {

        // **** initialization ****
        StringBuilder sb = new StringBuilder();

        // **** traverse the input string ****
        for (int i = 0; i < str.length(); i++) {

            // **** get character ****
            char ch = str.charAt(i);

            // **** process ch ****
            if (ch == '#') {
                if (sb.length() > 0)
                    sb.deleteCharAt(sb.length() - 1);
            } else {
                sb.append(ch);
            }     
        }

        // **** return final string ****
        return sb.toString();
    }

This is the function of interest in this problem. We also mimic the operation of the delete key on a keyboard but instead of using a stack we use a StringBuilder. We could have used a String but due to the fact that strings are immutable, the execution impact would be much higher.

In the main loop we traverse the specified string from left to right. We operate on the string mimicking what we do with a keyboard which is similar to what we did with stacks. As I am typing this post and looking at the code on a text editor, I guess we could have traversed the string one character at a time using the toCharArray() method of the String class. Not sure if that would be any faster, but it is worth while giving it a try. OK, I did try it and the execution stats remain unchanged.

Once we have a character we process it. If the character is ‘delete’ (#) we check if the string has at least one character (we use the length of the StringBuilder class) and delete the last character; otherwise we just append the character to the StringBuilder.

When done we return a String representation of the StringBuilder.

Note that the logic in this function is very similar to the one used in the stack function.

I hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 3218 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

E-mail:  john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.