Road to Google – Part 4 Typed Out Strings Ⅰ: Brute Force

Question:

Given two strings S and T, return if they equal when both are typed out. Any ‘#’ that appears in the string counts as a backspace.

Description:

Strings are a list of alphanumeric elements that are combined together and surrounded by quotes. So, as you can see in image 01, it can be considered as an array.

And what the question asks you about is, let’s say you’ve given the string “cb#d”. And you start typing “cb…” and then you type “#”. As written in the question “Any ‘#’ that appears in the string counts as a backspace“, the “#” will delete “b”. And finally, you type “d”. So, what you get is “cd”.

So, when you get the two strings: S:”ac#d” T:”az#d”, they will end up with the same format, proofing they are equal to each other. Did you get what the question is asking for?

Code:

And this is the actual coding solution. So what’s going on here is that you’re given two strings: “ac#d” and “az#d” nd compare the final forms of the two.

The logic behind this coding solution is to add an alphanumerical character to the variable idx (index) that keeps track of the current form of the strings. If the loop iteration hits “#” it removes the character before it with “idx–” in line 18.

So, the hardest part is probably line 11. Let’s take a deep look into it and see what’s going on there.

“s.substring(0, idx)” is taking the original string from 0 to the end of it.

s.substring(0, idx)

So, at this moment, the given string “ac#d” is taken thanks to the substring function.

Then “s.charAt(i)” iterates through the string and checks each character if there are any “#”. If it’s not “#”, it adds the character to idx.

s.charAt(i)

And then “s.substring(idx + 1)” moves the iteration to the next character.

s.substring(idx + 1)

And in the next if-block, if it hits “#” and as long as idx is more than 0, it subtracts from idx, meaning it pops out the character before “#”.

} else if (s.charAt(i) == '#' && idx >= 0) {
                idx--;
}

And this is the executed result.

$ java TypedOutString
True

For the record, this is the actual code:

import java.io.*;

public class TypedOutString {
    public static String removeBackspaces(String s) {
        int n = s.length();

        int idx = 0;

        for (int i = 0; i < n; i++) {
            if (s.charAt(i) != '#') {
                s = s.substring(0, idx) + s.charAt(i) + s.substring(idx + 1);
                idx++;
            } else if (s.charAt(i) == '#' && idx >= 0) {
                idx--;
            }

            if (idx < 0) {
                idx = 0;
            }
        }
        return s.substring(0,idx);
    }

    public static void main(String[] args) {
        String s = "ac#d";
        String t = "az#d";

        if (removeBackspaces(s).equals(removeBackspaces(t))) {
            System.out.println("True");
        } else {
            System.out.println("False");
        }
    }
    
}