The Self-Taught Computer Scientist

Introduction to Algorithms
56
Anagrams sometimes contain multiple words and include uppercase and lowercase letters, so you 
start your function by removing spaces from your strings and converting all the characters to lowercase:
s1 = s1.replace(' ','').lower()
s2 = s2.replace(' ','').lower()
You then sort both strings and compare the result to determine whether they are the same. If they 
are, the strings are anagrams, and you return 
True
. Otherwise, they are not, and you return 
False
.
if sorted(s1) == sorted(s2):
return True
else:
return False
Because your algorithm to detect anagrams relies on Python’s built- in 
sorted
function, its run time 
is O(
n log n).
Palindrome Detection
A palindrome is a word that reads the same backward as forward. 
Hannah, mom, wow, and racecar are 
all examples of palindromes. There are several ways to determine whether a string is a palindrome. 
One way is to copy the string, reverse it, and compare it to the original. If they are equal, the string 
is a palindrome.
Here is how to reverse a string in Python:
print("blackswan"[::- 1])
>> nawskcalb
Here is how to check whether a string is a palindrome:
def is_palindrome(s1):
if s1.lower() == s1[::- 1].lower():
return True
return False
First, you use Python’s built- in 
lower
function to make sure capitalization doesn’t affect your 
comparison. Then, you use Python’s slicing syntax to reverse the string and compare it to the original:
if s1.lower() == s1[::- 1].lower():
If the two strings are the same, the string is a palindrome, and you return 
True
:
return True

---

Chapter 5 String Algorithms
57
Otherwise, the strings are not palindromes, and you return 
False
:
Return False
The slowest part of your algorithm to detect palindromes is Python’s syntax for reversing a list. 
Because Python has to visit every item in a list to reverse it, the run time to reverse a list is O(
n), which 
makes your algorithm’s run time O(
n) as well.
Last Digit
Another common interview question is to return the rightmost digit in a string. For example, given 
the string 
"Buy 1 get 2 free"
, your function should return the number 2.
One elegant way to solve this problem is to use Python’s list comprehension feature. A list com-