Clear Digits - Leetcode 3174 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today let's solve the problem clear digits. In this problem we're given an input string S and what we want to do is remove every single digit from the input string and every time we end up removing a digit, we want to remove the closest non-digit character to the left of it. They also tell us that we want to do so by deleting the first digit. So in this example over here, we have two digits. The first one is three so they tell us that that's the one that we would want to delete, but I can tell you that it actually doesn't matter which order we do these. Given the constraints and the operation that we're doing, it's going to end up the same either way. So take a look at this example over here. We do not have any digits so actually there's nothing for us to remove. So we would just return the input string itself. In this second example though, we would go through the input string. Anytime we see a digit, I guess you could say that we would skip that digit. So in a sense you could say we're going character building the output. We see a character, we add it. We see a character, we add it. We see a digit, we skip that digit, but not only that, we would then remove the previous character that we've already actually added to the string. So we do not then have the B. The reason we add the B first is because we have no idea what's coming up ahead since we're going through this from left to right. Next, we see another character which happens to be a digit. It's four. We would skip it and we would also remove the previous character that already added to the input string or to the output string rather. So then we would end up with just an empty string. And so that is the correct output for this example here. Now you might be wondering what would happen if we had a case like this. Like maybe we have a character and then we have two digits that come after it. They don't really make that super clear with the problem description, but at the bottom they tell us that the inputs are generated such that it's always possible to delete all the digits. So I take that to mean that for every digit there's always going to be enough preceding characters so that anytime we do remove a digit, we are going to be removing a character. So I don't think an example like this is actually possible. So we don't really have to worry about that. Now if you are noticing in the dry run that I did earlier where we had a or rather C B 3 4 and we were adding characters to the string and then removing them from the end of the string, that's pretty much like a stack. So that is one valid way to solve this problem. Rather than creating a string, we actually create an array of characters which is pretty much a stack and then at the end we could just join those characters together to actually build the output string. Another solution, the first one that I actually coded up was this, just going through the input in reverse order because then anytime we see a character, we could yes skip that character, but instead of removing the upcoming non-digit characters immediately, we could just keep track of like a count, like our delete count and so after we see this, our delete count would be one. When we see this, our delete count would then be incremented to two. And then when we see a character, since our count is positive, we know that we can skip it and then we could just decrement the count and take it down to be one. Now we see another character, so we skip it, we take our count down to be zero. Now imagine we had additional characters here. Maybe we have an A. Now since our count is actually zero, we are not going to delete this character. So this one would actually stay and so we would add it to whatever data structure that we want, probably an array, and then I continue. I think this is also a valid way to do it. Since the solution is easy enough to code up both ways, I guess I'll show you the solution for both. It's going to be a linear time solution. In terms of space, since we are kind of using an intermediate array rather than building like the output string, I guess the output, like the extra space could be considered linear, but this is pretty much what we're returning. The reason we're putting it in the form of an array rather than a string is because in most languages, strings are immutable. So if we were to be updating that string, it would be less efficient in terms of time. Anyways, let's code it up now. So I'll show you the reverse order solution first. So what we're going to have is our result. It's going to be an array and we're going to have that delete count that I was talking about. Initially it'll be zero. We're going to go through the input in reverse order. So we can do this in Python, just reverse this iterator. And what we want to check is if the character at index I is a digit and thankfully that's actually a built-in function. So we could do this, S at index I {dot} is digit. If it is a digit, we will skip that character, but we want to increment our delete count. Now there's a couple other cases. One is if it's not a digit, but our delete count is positive. So this. Well in that case we also want to skip that character, but this time we want to actually decrement our delete count cuz we're basically deleting a character. The last case is going to be it wasn't a digit and our delete count was zero. So thus we can actually take the character and add it to our result. Notice that we are going through this in reverse order. So the result will also be built in reverse order. That's kind of a negative of the solution. So when you return, normally we could do something like this in Python, use the empty string as the delimiter and then join all the substrings together like this, but we actually want to go through the strings in reverse order. So we're actually going to reverse that like this in Python. So I'll run this to show you that it works and you can see that over here. If you didn't want to use this built-in function, it's actually pretty easy to implement it ourselves. So we could do something like this, is digit, passing in a character and what we would want is to get the ASCII value of that character which we can do like this in Python. We want to make sure it's in between the digit zero and the digit nine. Those are going to be in consecutive in ASCII. So whatever ASCII value belongs to zero, the one for one is going to be one more than that. The one for two is going to be one more than that all the way up until nine. So we can do something like this, take the ASCII value of nine, make sure that this is less than or equal to that. And in Python you can actually do inequalities like this, making sure that this is also greater than or equal to that. So we can just return the result of this boolean or this expression rather. So I'll run this as well. Well actually I should probably change this over here. So let me instead pass the character in to that function that we just created over here. So now let's run it. And here you can see that this works as well. I think it's about as efficient. It's just that on LeetCode like these kind of vary between whether it's 1 millisecond or 3. I think that's just random. If we wanted to treat the result more as a stack, what we could do is this. I guess we could keep this function, but then we could go through the string from left to right just like this and assuming we're building it from left to right, we probably wouldn't need to reverse the result over here. So we could get rid of that. But then in here, we could do something like this. If is digit, then we assume the stack is non-empty, the result is non-empty. So we could just pop from it. Otherwise, it's a non-digit character. So we could just add it to the result like this. Running this code, you can see here that it also works and I think it's about as efficient. If you found this helpful, check out neatcode.io for a lot more. Thanks for watching and I'll see you soon.