Reversing a String Using a Custom Algorithm

00:00 In this lesson, you will learn to reverse a string by writing your very own string reversal algorithm. Note that the algorithm described in this lesson is only one of many possible approaches. Before diving in, you’ll need a few tools to accomplish this task.

00:16 Python has a neat language feature referred to as tuple unpacking. It can be used to assign the elements of a tuple to multiple variables in a single statement. It can also be used to swap variables.

00:28 Let’s assign the values of 1 and 2 to the variables a and b. The variables b and a can be packed into a tuple and then unpacked in the same statements into the variables a and b. This effectively swaps their values.

00:46 One potential algorithm for reversing a string is to incrementally swap the left and right characters of a given string. This type of approach is usually referred to as a two-pointer solution.

00:57 In this case, the two pointers would be a left pointer and a right pointer. These pointers are integers which point to the elements to be swapped. Let’s go through an iteration of the string reversal algorithm.

01:09 If you want to have a closer look at the image you see on this slide, you can find it in high resolution in the materials for this course. In the first step, the pointer would start at the zeroth index, pointing to the first character, and the right pointer would start at the end, pointing to the last character.

01:26 The characters at those locations are then swapped. The left pointer is then incremented by one, with the right pointer being decremented by one. This is done repeatedly until the left and right pointers meet, at which point all characters have been swapped. For example, let’s say you want to reverse the string "HELLO". During the first iteration, the "H" and "O" would be swapped, as the left pointer is equal to 0, and the right pointer is equal to 4. During the second iteration, the left pointer has now been incremented to 1, with the right having been decremented to 3. Therefore, the "E" and the "L" would be swapped. During the third and final iteration, the left and right pointers would both equal 2, and therefore the algorithm would exit, returning the string, "OLLEH".

02:15 Let’s implement this algorithm in a function called reverse_string().

02:20 It takes in a single argument, a string, and returns that string with the characters in reverse order. During each iteration of the algorithm, the characters pointed at by the left and right pointers are swapped. However, strings are immutable, meaning that they cannot be changed. Therefore, it is better to work with a mutable sequence that will store our characters, such as a list. The swap operations can then be performed on this list, and once the algorithm exits, the list can be joined back into a string.

02:51 Next, let’s initialize the left and right pointers to point to the start and the end of our list, respectively.

02:59 Recall that the string reverse algorithm runs until the left and right pointers are equal. A common way to do this is with a conditional while loop, with the condition being that the left pointer must be lesser than the right.

03:12 If that condition check fails, the loop will exit. Inside the loop, you can use the tuple packing trick you learned earlier to swap the characters at the location pointed at by the left and right pointers.

03:26 Finally, the left and right pointers should be incremented and decremented, respectively.

03:34 Once the while loop is exited, all the characters should be in the correct order within your list. .join() can be used to combine this list back into a string, and this can be directly returned.

03:51 Let’s test this out on the string "Hello" from before.

03:56 Great. By leveraging Python features such as tuple unpacking and using a two-pointer approach, you can implement your very own custom string reversal algorithm.

04:06 Writing a custom algorithm is not usually recommended when preexisting solutions exist. It is, however, an important part of the learning process and plays a significant role in technical interviews.

04:19 Now that you’ve learned quite a bit about how to reverse the string, let’s recap the content of this course in the last lesson.