How to Reverse a String in JavaScript Without Using the Reverse Array Method

hi guys so in this video i'm going to show you three ways to reverse a string and two of them or without using the reverse array method so it could be a job interview question and i'm going to discuss the performance of each of the algorithms so the first one i'm going to show you is what's known as like the brute force way um or naive way which is a bit mean but whatever and so first so we're going to write a function called reverse string so rev string is going to take in a string and then we're going to declare a variable called r for array i'm just going to put that equal to an empty array and we're going to then create an array out of the string so we're going to do that i'm going to call it char's array so characters array and we're going to put that equal to string dot split and we're going to pass in an empty string so what does it takes it takes the string and puts each of the characters into an array so i'm going to show you what that is now so characters array we'll return that and we'll console.log rev string and let's just pass in my name save that and as we can see each of the characters in the string has been put into an array so this is a really useful method that you want to remember because it allows you now to use array methods on what was essentially a string so it's really useful so now what we're going to do is we're going to loop over this array starting at the very last item so y and we're going to push it onto the this empty array so we're going to build up this array in reverse into this so we're going to start with a for loop and we're going to put i equals to the characters array.length minus one so that's the very last index where y is and we're going to go we're going to loop up to i equals zero so the very first index which is where d is and we're going to decrement i by one each time now what we need to do is we need to get our array this empty array and push on the value from the characters array so we're going to start at the very last index for the first loop through i is going to be equal to zero one two three four okay so characters array four is going to be equal to y and we're pushing it onto this array next run three we decrease i by one so we're now here and we're going to push it onto the this array so that's going to build up the array in reverse so there we go so now what we need to do is turn this back into a string and to do that dead easy we'll just use the join method pass in an empty string and voila there we go there's the string reversed so it's pretty simple way of doing it really without using the reverse array method but what is the performance of this well the split method this built-in split method has to loop over every item in the string to put it into an array so the longer the string the more calculations this is going to have to do so if we have a string of length n n items long um this is going to have to do n calculations right so the longer the string the more the calculations need to be done here and again we're looping over every item in this array so again that's another n calculations and and remember the length of the string so that's n plus n so we're at 2n now and then here when we join it all up we've again got a loop over every item in this array and this array is n items long it's the same length as the string it's the same length as characteristic so we've got n plus n plus n which is three n so we've got roughly three n operations three times the length of the string that's the number of operations we got but what is the big o well if you remember if you watched my last video on big o you'll know that we just ignore this three because if n is a really big number we're passing a really big string which is say infinity characters long three times infinity is still just infinity it's just a very very big number so it just boils down to n so we say that this algorithm has a big o of n so can we improve on this we can improve on this um we can't improve the big o but we can improve the efficiency of the algorithm in terms of time so we can do that using what are called pointers okay so i'm going to define another function called rev string um it's going to take a string and this time we're not going to assign this array variable to an empty array like we did before we're going to assign it to um new array and we're going to say string dot length and what's that what that's going to do is it's going to create an array that is the length of the string long so i'll show you what that means we'll just log that out and we'll just use my name again so if we save that now we've got an array that is empty but it has five empty spaces in it and the reason we're doing this is because when we loop through the this array and build up we can build up now from both ends we can have a pointer pointing at this first item and we can have another pointer pointing at this right item and we can build it up from both sides and when these pointers meet in the middle then we can stop so now we only have to loop through half the length of the array which is going to save us some operations so let's define our character's array again same as before we're going to split the string up into an array of characters and then we need to define our pointers so we're going to say the left pointer is going to point at zero so index zero the very first item in this character's array okay which would be d it's going to point at d index zero and then we're going to have another pointer called right which is going to point to the very last index which is our characters array dot length minus one so that's pointing at the y essentially the very last index at zero one two three four so this is going to be equal to four okay and now we can write a while loop and we can say that while the left is less than or equal to the right we can then do some stuff so we can say the left the very first item in this empty array which is this right this right here we're going to put the very first item equal to the very last item from our characters array which will be y okay so essentially we're building up and reversed like before so we're going to say array left so the first run through this is going to be equal to zero we're going to put it equal to our characters array so chars are right the very last item and we're going to say the very last item in this array we're going to put it equal to the very first item from our characters array which is d okay so we're going to put that equal to characters array left and then we can increment the left pointer by one and decrement the right pointer by one okay and as you can see it's built up the array in reverse so i'll just go through that now so the first run through left is going to be equal to zero right is going to be equal to four pointing at the very right hand side we're going to get the this empty array we're going to say the first item in this array should be equal to the very last item in this array and then we say the very last item in this empty array is going to be equal to the very first item from our characters array then we increment the left by one so the left is now pointing at a and we decrement the right by one so the right is now pointing at n okay and then again we would do all this stuff until the left and the right meet in the middle and then we're done we've built up this array backwards and now we can just again join it up into a string like so and there we go so why is this better than the first one in terms of performance in terms of time well it still has the split method which is again a big o of n and the join which is again a big o of n but this bit in the middle um it only loops over the array half the number of times right because as soon as they meet in the middle once we've looked over half the array and these pointers meet in the middle we're done so if we've got an array that's a thousand items long this is going to be 500 operations less than this one because it's going to be half the number of loops in the middle so it still has a big o of n because er bigger is looking at the worst case and we're still using these methods which are a bigger of n but it's still more performant than the first one because we're only looping over half the number arrays here now the disadvantage of this is that it stores one extra variable in memory so it does take a little bit more space up in memory but that really isn't a big deal it's just one extra variable and we're saving potentially quite a lot of operations in the middle so that being said let's now show you the easy peasy way of doing it which is essentially just one line of code so i can write a function call it rev string three and we're just going to return the string split it up into an array and then we can use the reverse method now this wasn't allowed in the question but in real life this is the way you do it because it's just obviously much cleaner and simple simpler and then we can just join it back up into an array in terms of performance let's just make sure it works first actually okay so in terms of performance this is basically the same as the first way i showed you because we're splitting the string okay and then we're reversing it and the reverse method is essentially just doing this it's going to have a big o of n and the return r.join again it's the same so essentially this is the same as the first method but it's just obviously a lot easier to read and there's a lot less code this is the most performant way of doing it and so if you really do need to if you've got really big strings that you're passing in then this might be a good way of doing it it'll save you some operations a bit of time uh it's also good to show off in a job interview because it shows that you understand um the performance of algorithms and big o and that you can optimize your algorithms a little bit more so yeah in real life you just use this one though but maybe this one if you really needed performance but i doubt you probably will you know unless you're using really big strings so that's about it for this video hopefully that was helpful and not too confusing thanks for watching and i'll see you in the next one

Channel: DoableDanny

Views: 182

Rating: 5 out of 5

Keywords:

Id: GqlaV-n5dP0

Length: 12min 32sec (752 seconds)

Published: Sun Jan 03 2021