Strings
A dictionary is a great way to do this:
def translate_leet(phrase):
"""Translates input into "leet-speak"."""
# START SOLUTION
translated = ""
leet_speak = {
'a': '@',
'o': '0',
'e': '3',
'l': '1',
's': '5',
't': '7',
}
for char in phrase:
translated += leet_speak.get(char.lower(), char)
return translated
What’s the runtime of this code? Take a moment and think about it; it’s a little harder than it seems.
Answer
It might feel like linear time, O(n), since we’re looping over each character, but this isn’t corect.
Notice what we do in the loop:
look up in a dictionary (constant time)
add new letters to the translated string
This latter part may feel like constant time, but it isn’t. Remember that strings are immutable in Python; you never really “add to a string”. Instead, you’re always building up a new string, and that string gets longer every time.
If we translate “hello”, our loop looks like:
translated = "h"
translated = "h3"
translated = "h31"
translated = "h311"
translated = "h3ll0"
Making a 5-character long string is 5 times as much work as making a 1-character long string, so we’re doing a linear thing inside of our already-linear loop. So our runtime is O(n ** 2).