Welcome back, everyone.
Hopefully everyone got a chance to try their hand at coming up with an optimal solution.
Now, remember, with a lot of these technical interview questions, there are many ways that you can
come up with a solution and they might all have the same space and time complexity, meaning there exists
multiple versions and variations of a optimal solution in this lesson.
I'm going to show you what I would do in order to come up with an optimal solution working off of our
brute force, but also adding some of that logical abstract thinking that we've been talking about this
course thus far.
So when we looked at our brute force solution, we knew that where we needed to optimize was in our
space complexity.
When we had it, we were coming up with a oh of A plus B space complexity because A represented the
size of our string S and B represented the size of our string T.
We would then take these respective strings and run them through some code that would give us back some
kind of scaling data structure, which in this case was an array that would hold the final format of
the string after transformation, transformation being, which characters do we remove if there are
hashes in the string?
So here we know that ABC hashtag D becomes Abdeh.
So we returned Abdeh and similarly with String T, it's the same idea.
It becomes Abde here.
So we had two of these arrays that would both hold whatever the final output of these strings were.
We would then compare the characters inside of these arrays in the exact same position in the arrays
to see if we had a match.
If we did, we would return.
True, if we didn't, we would return false.
But the key here is to realize that the question really is only asking us to return, true or false,
we are choosing to create these data structures, these scaling in memory data structures in order to
help us get to this final answer.
But the question itself does not require us to even create these data structures in the first place.
So that is our first hint that if we know for certain there's no real need for these other than the
fact that our solution depends upon it, our brute force solution in this case, then maybe there is
a way for us to remove this, because if the question required us to return these arrays instead, then
there's no way around it.
You have to create them in your code because the question expects you to create them as part of the
answer.
But our question is simply asking us to return, true or false, depending on the condition, if these
two strings, when typed out, have the same output.
So that might be a way to bring down the memory is to remove these and find some other way to figure
out whether or not it's true or false that these two strings are equal when transformed.
So we'll talk about that next.
But first, let's just get rid of these arrays here.
So knowing what we know now, perhaps what we can think about is some of those hints I gave you, which
is about using the 2.0 structure, if there was a way where we can think about if we had two pointers,
one pointer pointing to an element and s and one points are pointing to an element and T and then just
comparing those letters, because if you were to break this problem down into smaller problems, when
we matched the characters in the arrays, we were matching them character by character, by the position
that they were in.
So similarly, we can move that out and just use the strings that we are given as the actual structure
that we should compare against, because we're really just comparing these strings anyways.
And we can compare whether or not the characters are equal in some position P in this case, maybe P1
and P2.
So I'm more clear here is the character at Espie one the same as the character in T P2.
Now, if we go from left to right, this becomes problematic because if we were to say this character
at P1 here.
And this character at P two, right here in the same place, let's say, right here.
If we were to compare these two, we know that this would not be true just upon evaluation, but then
if we were to look out a little bit and think about the strings themselves, we know that this hash
is going to delete the sea and we know that these two hashes are going to delete these two values.
So this hash is actually going to delete the Z anyways.
So just by comparing these letters, this is not going to work because our backspace deletes backwards
and our points are moving left to right is always going to be one or two steps behind.
In fact, it could be multiple steps behind, depending on how far down multiple hashes might be, because
a row of hashes is going to delete a row of respective characters.
But if we go from left to right, we won't see those hash tags until much later.
So we know that our logic cannot work this way.
Instead, what we can do is knowing that the hash is delete from right to left, then we just move our
pointers and start them from the right instead of starting them from the left.
So here we can initialize P1 at the end of string S and P two at the end of string T, logically speaking
here, because we're starting at the very end, meaning the right side, we know that there are no characters
after this character that we're currently pointed on because it's the last character, which means that
if this character is not a hash, then this character ends up in the final string.
This D is the last character right here in our final string.
Whatever this character is means that this character must be in the final string.
This then means that we don't have to worry about this character being deleted so we can compare this
character, a P one with this character at P two, because both of these characters must be in the final
string format that gets transformed from whatever the string is.
So that means that if the string up one and the string character have to match, then we know we can
move our pointers forward to check the rest of the strings respectively.
If it does not match, then we know that we got a return false because these characters, if they don't
match, means that the character in the final strings don't match.
Which means that we have our answer about this being false.
If they match, what we're going to do is we're just going to move the characters one forward or the
pointers.
So in this case, P two is going to move here and P one is going to move here.
Now, what we do when we encounter a hash tag is we think, OK, there's no point in us comparing these
hashes because what these hashes do is they delete a character.
So what we can then say is that here I want to move my pointer over by two, because what we need to
do is we need to move over to the C and then over again to the B, because the C is going to get deleted,
which means that the logic and rationale here is that I want to remove these two characters, logically
speaking, without actually modifying anything in memory.
So the easiest way to do that is just to move.
This points are over by two, but we're actually not just going to skip P one all the way over to B,
which is two places over, because what we need to see is that if this character here is a hash or if
it's a character, as we see in our string t, so I know that here I just moved it over.
But let's just evaluate why we got to do it step by step.
So here we know that we have two pointing to some hash value.
We can then say that he, too, needs to move left over by two characters, so we're going to move it
over once first.
So PETA is going to move over on consumer step.
This means that PETA moves over by one.
And we have one more step to make from here.
We then evaluate, is this character a hash or is it a letter or some kind of strong character?
In this case, it's another hash, which means that this has to delete another value to the left.
We do not simply delete this character with this first hash, we kind of group these two values together
in a way to see how many characters to the left are there actually to delete.
So because we have another hash, we have another two characters to move over to.
So we have to add two to the number of steps we have yet to make.
And here we then move pizza over again, because there's three steps to be taken, so we move it over
by one and then this three goes down to two.
So then we ask, is the character up to a hash, it's not so we don't need to add any values to the
number of steps we have to take.
We can now just move it over by one and decrement the count.
So now we ask again, is the character up to a hash, it's not.
So once again, we see how many steps we have left.
We have one more, so we decrements it by one.
And then we move to over.
And now we see we have no more steps to take, so we've accounted for all the hashes from when we first
saw our first hash and now P to AMPE one are both in their final places as far as the strings that might
have had any hashes before it.
So we know for sure then that wherever pizza is and wherever P one is is out of character that will
end up in the final string.
So here we see that B and B are in and we can say then OK P one, MP two, do these characters match?
They do.
So then we can now move P1 and P2 over once again.
We check do these final characters match, they do, so we know them for sure, we've explored the full
string on both sides and we can say that conclusively.
We know that this should return true.
The final format of these two strings to match, and that is the technique for using two pointers,
as well as leveraging the strings that were input to us as a way to evaluate whether or not we have
a matching string after the final transformation.
The key to the logic here was realizing that these hashes would be moving a character to the left,
so in order to account for it with pointers, then we have to account for it by starting from the right
of each string.
So that's really the big logical jump that we had to make while using this to point to structure.
And we see now that with this optimal solution, we are actually storing anything in memory.
So chances are we've managed to bring down our actual memory usage.
So with that, I want you to try and code out the solution that we came up with.
I'm going to show you in the next lesson, but I wanted you to try it first.
I'll see you in the next lesson.