OneAway - Crack Coding Interviews

Okay, here's the question. So, there are three types of edits that can be performed on strings. Insert a character, remove a character, or replace a character. Given two strings, write a function to check if they are one edit away. So, what this means is, let's look at some examples. If I have two strings, pale and ple, and if I insert one character a in the second string, and that's going to become the first string. So, this will be true because that's just one edit away. We insert one character. Let's look at the second example. We have pales and we have pale. So, and if I remove one character from the first one, it's going to become the second string. So, this will also return true. Likewise, for the third one, if I replace b with p, then they are going to be the same. So, it's also true. And lastly, here, I would have to do two edits. Here, I would have to insert an l and replace b with p in order for the second one to become the first string. So, this will be false because it takes two edits for the two strings to be the same. So, basically, the arguments of the method will be two strings and output will be a boolean, right? So, let's just lay out the structure here. I'm going to have a boolean here. If it's one edit away, and it's going to take two strings. Let's just call them s1 and s2. Okay. So, before we dive into the actual logic, let's really think about what this means, right? So, first, let's talk about replace. What does replace mean? It will be in the case of this example here. A replace means that the two strings are exactly the same. So, their characters are matching each other in each position except for one, right? It could be at any position, but there's one and only one character that are different. So, in that case, we also notice that the length of these two strings has to be the same. If they're not the same, there's no way we can replace a character and make one become the other one. So, first of all, they have to be of the same length, and second of all, they had to be only one character different. Okay. That's what replace means. Let's look at what insert and remove means. Let's first look at insert. So, an insert basically means if I go through both strings, character by character, right? And at some point, for example, in this case, it will be the second position. At some point, I'm going to encounter two characters that are different. However, when the longer string, I move the pointer one more position, the rest of the string is going to be the same, right? So, let me repeat that again. So, if I go through the two strings, character by character, by using two pointers, so position one, they're both p. Position number two, one is a, one is l. And we take the pointer of the longer string and move it one forward, it becomes l, and l will be the same, and the rest of the string will be the same. That's what insert means. So, they should be the same except for, they will be the same when we shift one pointer forward of the longer string. Likewise, for remove, you may have noticed that a remove is essentially the reverse of the insert, right? So, if I can remove a character of the first string for it to become the second character, the second string, that would be the same as saying if I insert, I can insert a character into the second string for it to become the first one, right? So, insert and remove, they're essentially the same thing. But next, let's also look at the length. For insert or remove, the two strings have to be of length difference one. They have to be one character away in length, right? So, all right. So, with that being said, let's delve into what the basic structure here. So, let's just say we're going to handle these scenarios, the three scenarios, actually in two methods. First, we're going to handle, this method is going to handle the replace scenario. It's just called canReplace, right? So, this is going to take, again, two strings, string1 and string2. All right. So, canReplace and another one will be canInsert or remove. Okay. Again, this takes two arguments. Both are of type string. Okay. All right. So, how do we decide which one to use? We just talked about that a moment ago. We're going to look at the length of the two strings, right? So, if string1.length is equal to the string2.length, we're going to use the replace logic, right? So, we're going to pass the same strings into this method here. Else if, because when we talk about the insert and replace, the length of these two strings matter because we want to move the, shift the pointer of the longer string. So, we need to be able to tell if s1 is longer than s2. So, in that case, let's just assume that whenever we call this function, s1 is shorter than s2. In other words, this is the same as saying I can insert a character into s1 to make it s2, right? So, this way, we always make sure that s1 is shorter and s2 is just one character longer. So, here, we can say if s1.length plus one is equal to s2.length, we're going to invoke this function here, return, pass the arguments, and else if, right? So, this time, if s1.length minus one is equal to s2.length, that means in this case, s2 is the shorter one. In this time, we can reuse the same method, but we have to reverse the order, right? Because we always assume that the first argument is going to be the shorter one and the second one is going to be the longer one. All right. So, if none of these scenarios are true, that means we cannot finish the task with one edit. So, it's going to return false, right? So, that would be the big picture here. Now, let's delve into how we can implement the logics. Let's start with replace. With replace, we just said that if two strings fit into the category of, if we replace one character, it becomes the second string. That means they should be the same except for just one position, right? So, what we're going to do is we're going to be looping through all the because once they enter here, they have the same length. So, we can just use one for loop, right? So, if i equals zero, i is less than s1.length, it doesn't matter if you use s1 or s2 because they're of the same length, and i plus, right? So, let's loop through them. While we're looping through them, we have to compare the values, right? So, let's just say if the values are not the same. So, if s1.character at i is not equal to the corresponding position at s2, that means we encountered the character that are different, right? If it's different, then we're going to say the difference is found. So, we need to have basically a Boolean variable to keep track of that for us. So, Boolean's variable is going to be called the difference initialized to false. So, this time we're going to say the difference is found. It's equal to true, okay? And just think about it. So, after this block, we found the difference and we reset this variable to true, and then it's going to go to the next iteration. When you go to the next iteration, in the happy path, it's going to be the same. So, we're not going to be entering this block again. If we ever have to enter this block again, that means it's not the scenario we want. That means there are more than one character that are different. We encounter a second different character. So, in that case, before we're setting the difference is found, we're going to do a check. If it's already there, so this one, if it's already set before, that means we already encountered different characters. So, this whole method will have to return false, right? Hopefully, that makes sense. And last but definitely not least, we have to return, if we go through everything and we only encounter this once, then this being set to true, we have to return true, right? So, and it could be that we never enter into this block again. That just means these two strings are identical and we need zero at this way, and that's acceptable. That's okay. So, we're still going to return true, okay? All right. So, that would be the logic for replace. Now, let's look at the logic for insert or remove. Because they are of different lengths, so we are going to keep two different pointers, right? So, we're going to say index one, start with zero, and we're going to have index two. It's also equal to zero, right? Make some space here. I'm going to make more space for you. Okay. Next, we're going to be looping through these two strings. We're going to say while index one is less than S1 dot length, and index two is less than index two dot length. The reason we're using and here instead of or is that if we're reaching the end of the string, that means we're reaching the end of the shorter string, and that should be the end of it. There's no point of comparing the rest, right? Because we already complete one string and we can already tell the result. All right. So, let's loop through this. Let's just handle scenario if they are different, okay? So, if they are different, at index one is not equal to index two. What does it mean? If they are different, right, and we increment the index of the longer string, and then the rest of it should be the same. But before we do that, we have to check if it's the first time or the second time you enter this block. There has to be one and only one time we enter this block, right? So, if it's the second time we enter this block, we're going to say we're going to define a Boolean variable. So, again, we're going to call difference found, initialize to false, right? So, if it's the first time, if it's the first time we're going to say difference found is equal to true, okay? However, if it's the second time, that means the difference is already found, we're basically going to say return false, right? So, this whole function will return false. All right, and then once he enters this, once he passes this stage, all the rest of the characters should always match. So, we're going to increment both index, index two plus, plus. And once we reach everything, this is going to return true, okay? Now, let's take this, put it into IDE and run this and see if it's actually going to work. Again, I'm going to be using IntelliJ. Let's put it here. Do I have a typo somewhere? Oh, I should be using s2.length. Okay, looks good. Next, let's write our main method. public static void min string args. Okay, this time I'm actually, all right, let's again mark each method as static. So, we don't have to create a new object each time we're calling the function. All right, so, let's print out the results. Print line, one away dot is one edit away. Let's use our example right here. So, pale and ple. Actually, I'm going to do this four times. So, first one is going to be pale and ple. And this one is going to be pales pale. Pales pale. Next one is going to be pale and pale. Last but not least, we have pale and bay. So, here we have pale and bay. So, and the expected result will be this one will return true and true true. Last one will be false. All right, let's go ahead and run this. Okay, now we have true true true and false. Okay, so, that'll be it. Next, let's talk about the time complexity. The time complexity, again, will be big O of n, where n is the length of the string, of the shorter string, actually. Like we talked about before, because there's just one character difference. So, it doesn't really make a big difference. And additionally, the algorithm is going to stop when we encounter the end of the shorter string anyway. So, it's going to be defined by big O of n.