Medium Interview Question

Python Coding Interviews: Tips & Best Practices James Uejio 17:58

In this lesson, you’ll use what you learned in the previous sections to solve a medium real world interview question. Medium means something you might find in a technical phone screen or an onsite interview.

Here’s the question:

Python
      
    
def keypad_string(keys):
    '''
    Given a string consisting of 0-9,
    find the string that is created using
    a standard phone keypad
    | 1        | 2 (abc) | 3 (def)  |
    | 4 (ghi)  | 5 (jkl) | 6 (mno)  |
    | 7 (pqrs) | 8 (tuv) | 9 (wxyz) |
    |     *    | 0 ( )   |     #    |
    You can ignore 1, and 0 corresponds to space
    >>> keypad_string("12345")
    'adgj'
    >>> keypad_string("4433555555666")
    'hello'
    >>> keypad_string("2022")
    'a b'
    >>> keypad_string("")
    ''
    >>> keypad_string("111")
    ''
    '''

The entire solution will be available at the end of the course. Try the problem yourself and then watch the video for the solution.

You heard about Big O analysis, which is a way to analyze the speed and memory usage of a function or block of code. See Wikipedia Time complexity for more information.

00:00 In this video, you’ll use some of the concepts you learned in this course to solve a medium-level interview problem. Let’s get started. Here’s a function keypad_string().

00:10 This function will take a string consisting of 0-9 and find the string that is created using a standard phone keypad. Here’s a standard phone keypad. 1, 2, 3, 4, 5, 6, 7, 8, 9, *, 0, #. 2 maps to (abc), 3 maps to (def), 4—(ghi), et cetera. 0 maps to space, 1 doesn’t map to anything, and same with * and #—don’t map to anything.

00:37 Let’s look at some tests. I wrote a bunch of tests, but the interviewer might not give you this many, so you should always try to come up with your own. Here is keypad_string() with the string "12345".

00:48 It returns a string 'adgj', because "1" corresponds to nothing, "2" corresponds to 'a'—because 2 is only pressed once—"3" corresponds to 'd', "4" corresponds to 'g', "5" corresponds to 'j'.

01:02 So, how do you get the second or third letter? Well, you have to press the number multiple times. So, "44335"—this many times—"666" is going to be the string 'hello', because "44" maps to the character 'h'—because you press it once, then twice.

01:18 "33" maps to 'e'. "55"—so, this "5" actually appears six times, because if you press the key more than this many times, then it will add the last letter and then sort of loop back around.

01:32 This corresponds to 'l', and then this corresponds to 'l'. "666" corresponds to 'o', because "6", "6", and then "6" again.

01:43 Here’s an example using the 0: "2022". "2" corresponds to 'a', "0" is a space, "22" corresponds to 'b'. Empty string should return empty string, and something just consisting of 1’s should also return the empty string. I highly recommend you try this on your own.

01:59 Maybe take—in this case—30 to 45 minutes to try to solve this problem. I will go over the solution in five, four, three, two, one.

02:09 What’s the first thing we should do? Well, there’s two steps. # build the map from keys to letters, so basically, how to map "2" to "abc", "3" to "def", et cetera.

02:21 Then, # loop through the keys and add the corresponding letter (taking into account keys pressed multiple times). So, this is going to be the harder of the two, but let’s start with building the map.

02:36 This is somewhere the string constants can come in handy. So, import string. What are the possible letters? Well, possible_letters are going to be string.ascii_lowercase. This is going to be 'a', 'b', 'c', 'd', 'e', 'f', 'g', all the way to 'z'. What are the possible keys?

02:55 possible_keys = string.digits. This is going to be the strings '0', '1', '2', '3', '4', all the way to '9'.

03:02 Then, we’ll need a variable for our final mapping—key_to_letters.

03:09 Then, we might need some more variables, but let’s just try to get started. So, for key in possible_keys, how do we know what to map? Well, let’s start with "0" and "1".

03:23 Those, we know for a fact, don’t really follow this rule of 'abcdefg', and they won’t even use the possible_letters. So, if key == "0": then key_to_letters[key] is going to be a space. if key == "1": then key_to_letters[key] is going to be the empty string.

03:46 Now, let’s look at this logi: how to build this dynamically so that we’re not just hardcoding each number. Well, you can think about it like this. Basically, it’s slicing three letters at a time, or sometimes four letters at a time, from the possible_letters.

04:04 So, how do you slice a string? Well, you can have a start index, so maybe start_index,

04:12 and then the letters is going to be equal to possible_letters sliced from the

04:19 start_index to the start_index + <some number here>. Well, it changes from 3 or 4, so let’s do something like, let’s put an else: because this should all be under here, and then something like num_letters.

04:36 This is the number of letters that we should be slicing. It’s going to be equal to 3, but if the key is in the set {"7", "9"}—so, instead of writing if key == "7" or key == "9", just put it in a set and do this in—it’s a lot cleaner.

04:57 num_letters = 4. So now, slicing possible_letters to start_index + num_letters, and then key_to_letters[key] = letters.

05:11 Let’s just print out the key_to_letters and make sure that this worked.

05:18 '0'—'abc', '1'—blank, '2'—'abc', '3'— 'abc', '4'—okay, so this clearly didn’t work. There are two issues.

05:27 '0' mapped to 'abc', which it shouldn’t have, and that’s because we forgot an elif, here, instead of an if, because if is going to execute this, then not execute this, and then execute the else. So—elif.

05:38 And then, it’s because we forgot to increment the start_index…

05:43 += num_letters.

05:48 '0' maps to space, '1' maps to empty string, '2'—'abc'. 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'.

05:58 Perfect. This is actually a perfect place to introduce a helper function to store all of this, because this is basically completely separate from what we need to do below, and sometimes it might be hard to keep scrolling up or read through the code.

06:13 It just gets a little confusing or maybe we’ll end up reusing variables, so let’s just put this all in a helper function. This will look really good in interviews when you start to compartmentalize code. Let’s call this, get_key_to_letters()…

06:31 and then return key_to_letters.

06:36 Now, just put that over there. key_to_letters = get_key_to_letters().

06:44 Save, make sure it worked. It worked correctly. Okay, so now the second part. # loop through the keys and add the corresponding letter (taking into account keys pressed multiple times).

06:53 So, let’s try to do the case where they aren’t pressed multiple times. Just do for key in keys and make a result.

07:03 result += key_to_letters[key], then maybe just the [0], just to be naive, and then return result.

07:15 So, this is going to error for some of them. Here, we got 'gg'—blah, blah, blah, blah, blah. It actually passed the first test, so that’s cool.

07:23 And here you get 'a aa', instead of 'b'. So now, we’ll definitely have to introduce a count to count the number of times the key has been pressed, and also the current key, because if the key changes, then we’ll need to reset the count, and in order to know if the key changed, you’ll need to introduce a new variable, curr_key. Okay.

07:47 Now, instead of doing this, what cases do we have? Well, we can do basically if key == the string "1", just pass, because basically, in those cases, do nothing. Otherwise, if there has been no curr_key pressed, then the curr_key = key and count = 1.

08:09 This is basically just doing the first letter, because curr_key will be nothing, and so you know that you’re not going to add anything to your resulting string yet, because nothing’s changed. You’re just pressing a key, you don’t know if that key is going to repeat or not, so let’s just do curr_key count equals 1. Otherwise, here, there are two possibilities: # press the same key, # press different key.

08:37 I guess a better name for this curr_key variable would actually be prev_key (previous key).

08:44 So then, # press the same key if prev_key == key. Let’s be very explicit so we don’t get confused.

08:57 Okay. Otherwise, # press different key. So, what’s the case if it presses the same key? Well, there are two cases here: # press X times already, X being the length of the letters that it maps to—for example, 5, 5, 5, and then 5, one more time.

09:15 You’ve pressed it already three times, so now you have to loop back to the beginning and then add that last letter. Otherwise, # hasn't pressed X times yet, so something like if count == len() of the length of the letters.

09:32 So, this will be curr_key_letters = key_to_letters[key]. len(curr_key_letters). Then, what do we do? Well, add to the result, the last letter… the last letter. Reset count to 1.

09:51 Otherwise, just increment count. Okay, so this takes care of the case where you press the same key. # press different key—well now, you need to look at the previous letters and add, basically, the letter that corresponds to the number of counts that you’ve done.

10:08 So, result += prev_letters[count - 1]. It’s - 1 because count starts at 1—you pressed it once, 2—you pressed it two times, but then to get the letter that corresponds to the second press would actually be the first index of the letters. And then prev_key = curr_key and then count = 1. I think this line was just legacy, so let’s remove it. Save. Python doctests. Okay, a bunch of errors, not surprising. letters, curr_key_letters—here.

10:42 Let’s see what else is yelling. key—this should be curr_key.

10:47 I think that’s good. 3 of 5 failed. Okay. It looks like we’re missing the last letter. Well, that’s because it goes "2", and then "0"—it will add the count for "2" and "0" goes to "2", it will add the space, and then "2", then "2", and then it will never change keys, so it will never add the 'b'.

11:08 So after here, we need to do something like result += curr_key_letters, indexed at count - 1.

11:19 Okay. 'curr_key_letters' […] local variable […] referenced before assignment. Okay. So, probably something like…

11:33 Redefine it there. Okay, string index out of range. I think this has to do with…unlocal—local variable 'curr_key'…here.

11:45 So, a better way would maybe do curr_key is going to be empty string, or you could do this to be fancy. And then, only do this if there is a curr_key. Oh.

12:01 string index out of range. result += curr_key length. So, I have to basically check because it could be the case that it could be all 1’s, and so then indexing count - 1, which would be -1 would not work, so I have to do something like if len() greater than 0, then add to the result. Perfect! So, it all passes.

12:23 Something you could add is adding in an assert statement to make sure that the key is a valid key. So, something like move this import so that it’s actually used globally,

12:34 and then something like digits here. Maybe set something like valid_keys = a set of string.digits and then

12:52 assert curr_key in valid_keys, otherwise, "Invalid key". Okay, that obviously works. But then, do something like keypad "*", then do something like "Traceback (most recent call last):",

13:19 do something like "AssertionError: Invalid key".

13:26 Cool! So, that passed. Let’s look at the runtime really quick. So, get_letters_to_key—this is actually taking constant time because even though it has to loop through "0" through "9" and do a bunch of stuff, it doesn’t depend on the input.

13:41 And so, really, you can think of it as constant time. Actually, it might be better to make this a global variable, something like

13:49 KEY_TO_LETTERS and then use it here, here, and I guess, here. Cool. Still works. So yeah—constant time, there. Here—constant, constant, constant.

14:04 This is constant because this length does not depend on the input. This takes O(n) time because you’re looping through n keys. Assertion is constant, constant—all constant. To access a dictionary is constant. Here—constant. len(curr_key_letters)—so, this is actually taking the length, which is constant. All this here, getting the dictionary—constant. result +=, here… So, this function takes O(n) time, where n is the size of the keys.

14:40 So, let’s quickly review the solution in its entirety. First, there’s a function get_key_to_letters(), which helps create a map key_to_letters.

14:47 This will help us find what each key, or what number, maps to. We took advantage of the string module and created the possible_letters, which is ascii_lowercase—'a', 'b', 'c', 'd', all the way to 'z'—and possible_keys, which is the digits '0' through '9'.

15:01 Then, we created the dictionary that is going to be our mapping, a start_index to see which possible letter we’re currently looking at. And then, we looped through all the keys. Two hardcoded cases for "0" and "1", because they don’t include any letters from ASCII lowers, and then created this variable num_letters = 3.

15:19 That’s the number of letters that maps to the current key. If the key is "7" or "9", then the number of letters that will map is 4. Then, slice the possible_letters—start_index sliced to start_index + num_letters.

15:32 So, this is going to pull this number of letters from the possible_letters. Then, map that in the dictionary and then increment the start_index, which is sort of our pointer, to which letter to start slicing at. Then, return the dictionary. Here’s a global variable that’s bound to get_key_to_letters(), so that way, every time we call keypad_string(), it doesn’t re-instantiate this map. This map will only get created once.

15:57 Now, scrolling down, here’s where most of the logic happens. Basically, we have a result which will be our resulting string, count to count the number of times a key has been pressed, prev_key, which would be the previous key, and curr_key, which is the current key we’re looking at.

16:11 Then, the valid_keys is going to be the set of all the digits. That way, we can validate if the key is a valid key by using the assert statement and then raising an error. So, if the current key is "1", then do nothing, because that’s a special case. Otherwise, if there’s no previous key, that means we’re at the first key, and the previous key equals the current key, and the number of times we’ve pressed is 1. And if there is a previous key, that means we’re at the second—or later—key, and then we get the letters that map to the key, check if the previous key is the same key, and there are two cases, here, where you’ve already pressed X times, where X is defined as either 3 or 4. Check if the length of the curr_key_letters is equal to the number of times you’ve pressed it already. And if it is, then you add to the result the last letter of the mapping, and then reset the count to 1.

16:59 Otherwise, you haven’t pressed it X times yet, so then just increment the count. And then the case where you’ve pressed a different key, then get the previous letter mapping—add to the result the last letter of that mapping, then reset the previous key to the current key and then count = 1. Then, you need this case at the end, because basically, if you’ve been pressing the same key, the key wouldn’t have changed and you won’t have added the correct letter at the end. So, check if there’s a curr_key. Basically, this is just checking if you’ve went through this for loop, then get the current mappings, then check if the length of the current key mapping is greater than 0, because it could be the case you’re pressing 0’s over and over again, and there is no mapping, and this [count - 1] will error.

17:39 So, if this check passes, then you add to the result the last letter. Then, you return result. This concludes this pretty long video where you went through a medium-level interview question.

17:50 In the next video, you’ll use the topics you learned in this course to solve a hard interview question.

belushkin on April 27, 2020

Here is my solution before watching the video:

def keypad_string(keys):
    '''
    >>> keypad_string("12345")
    'adgj'
    >>> keypad_string("4433555555666")
    'hello'
    >>> keypad_string("2022")
    'a b'
    >>> keypad_string("")
    ''
    >>> keypad_string("111")
    ''
    >>> keypad_string("7773325550799984466666")
    'real python'
    '''

    keypad = {
            '1': '',
            '2': 'a',
            '22': 'b',
            '222': 'c',
            '3': 'd',
            '33': 'e',
            '333': 'f',
            '4': 'g',
            '44': 'h',
            '444': 'i',
            '5': 'j',
            '55': 'k',
            '555': 'l',
            '6': 'm',
            '66': 'n',
            '666': 'o',
            '7': 'p',
            '77': 'q',
            '777': 'r',
            '7777': 's',
            '8': 't',
            '88': 'u',
            '888': 'v',
            '9': 'w',
            '99': 'x',
            '999': 'y',
            '9999': 'z',
            '0': ' ',
            '': ''
    }

    s = ''
    res = ''
    for letter in keys:
        if len(s) > 0 and (s[-1] != letter or (s+letter) not in keypad):
            res += keypad[s]
            s = ''

        s += letter

    res += keypad[s]
    return res

efimius on April 27, 2020

@belushkin agree much simple and easier to follow

James Uejio RP Team on April 27, 2020

@belushkin thank you for sharing your solution! I agree your solution is better. I was trying to incorporate some topics into a solution and make it more dynamic. But after the fact I realized hard coding might have been better.

Ksenia on April 28, 2020

import string

def get_key_to_letters():
    KEY_TO_LETTERS = {}
    letters = string.ascii_lowercase
    digits = string.digits
    i = 0
    for key in digits:
        if key == '0':
            KEY_TO_LETTERS[key] = ' '
        elif key == '1':
            KEY_TO_LETTERS[key] = ''
        else:
            num_letters = 3
            if key in {'7', '9'}:
                num_letters = 4
            KEY_TO_LETTERS[key] = letters[i:i + num_letters]
            i += num_letters
    return KEY_TO_LETTERS

KEY_TO_LETTERS = get_key_to_letters()   #   O(1)

def keypad_string(keys):
    '''
    Given a string consisting of 0-9, find the string that is created using a standard phone keypad
    | 1        | 2 (abc) | 3 (def)  |
    | 4 (ghi)  | 5 (jkl) | 6 (mno)  |
    | 7 (pqrs) | 8 (tuv) | 9 (wxyz) |
    |     *    | 0 ()    |     #    |
    You can ignore 1, and 0 corresponds to space
    >>> keypad_string('44444445566')
    'iigkn'
    >>> keypad_string("2345")
    'adgj'
    >>> keypad_string("4433555555666")
    'hello'
    >>> keypad_string("2022")
    'a b'
    >>> keypad_string("")
    ''
    >>> keypad_string('4445566')
    'ikn'
    >>> keypad_string("*")
    Traceback (most recent call last):
    ...
    AssertionError: Invalid key
    '''
    # 1. build the map from keys to letters
    # 2. Loop through the keys and add the corresponding letter
    # (taking into account keys pressed multiple times)

    if keys == '':
        return ''
    valid_keys = set(string.digits)
    i = 0
    message = ''
    while i < len(keys):
        assert keys[i] in valid_keys, "Invalid key"
        j = i
        if (j + 1) == len(keys):
            pass
        else:
            while keys[j] == keys[j + 1]:
                if (j + 1) == len(keys) - 1:
                    j += 1
                    break
                else:
                    j += 1
        size_of_keypad_str = len(KEY_TO_LETTERS[keys[i]])
        if (j - i) < size_of_keypad_str:
            message = message + KEY_TO_LETTERS[keys[i]][j - i]
        else:
            count = (j - i) // size_of_keypad_str
            letter = KEY_TO_LETTERS[keys[i]][-1]
            message = message + letter * count
            residual = (j - i) % size_of_keypad_str
            message = message + KEY_TO_LETTERS[keys[i]][residual]
        i = i + (j - i) + 1
    return message

AlekS on April 28, 2020

from collections import deque

inp = '255533990625533777702077776668866300***0099990099990999999999999444664'

# map homogeneous group to characters e.g. "88888" to 'vt'


def map_to_letter(seq):

    switcher = {
        '0': ' ',
        '1': '',
        '2': "abc",
        '3': "def",
        '4': "ghi",
        '5': "jkl",
        '6': "mno",
        '7': "pqrs",
        '8': "tuv",
        '9': "wxyz",
        '*': '*',
        '#': '#'
    }

    div4 = (len(seq) - 1) // 4
    div3 = (len(seq) - 1) // 3

    if seq[0] in ['1', '*', '#', '0']:
        return switcher.get(seq[0]) * len(seq)

    if seq[0] in ['7', '9']:
        return switcher.get(seq[0])[3] * div4 + switcher.get(seq[0])[len(seq) - (4 * div4 + 1)]

    if seq[0] in ['2', '3', '4', '5', '6', '8']:
        return switcher.get(seq[0])[2] * div3 + switcher.get(seq[0])[len(seq) - (3 * div3 + 1)]

#split given sequence to homogeneous groups e.g. '233311444422' to '2_333_11_44444_22'


def split_to_groups(lst):
    qe = deque(inp)
    res = []
    prev = lst[0]
    while qe:
        curr = qe.popleft()
        if curr == prev:
            res.append(prev)
        else:
            res.append("_")
            res.append(curr)
        prev = curr

    res0 = ''.join(res)
    result = res0.split('_')
    return result

# joining mapped letters to string e.g. ['a', 'l', 'e'] to 'ale'


def join_to_string(inp):
    return ''.join([map_to_letter(each) for each in split_to_groups(inp)])


assert 'alex makes a sound  ***  z  z zzzing' == join_to_string(inp)

WD on April 30, 2020

This function does not account for the case where someone wants to type two consecutive letters which use the same key. Ex: ‘wade’ would require the user to press ‘9’ for ‘w’, ‘2’ for ‘a’, ‘3’ for ‘d’, and then ‘33’ for ‘e’. However, without inserting a space or some other technique like a time gap between the ‘3’ for ‘d’ and the ‘33’ for ‘e’, the function will see it as ‘333’ for ‘f’ and output ‘waf’ instead of ‘wade’.

fergusmeiklejohn on May 7, 2020

How interesting :-) I did it a completely different way, with List Comprehensions. I’m not sure if this solution is better though, it must be a slower I’d have thought:

    num_dict = {
        "1": '', "11": '', "111": '', "2": 'a', "22": 'b', "222": 'c', "3": 'd', "33": 'e', "333": 'f', "4": 'g',
        "44": 'h', "444": 'i', "5": 'j', "55": 'k', "555": 'l', "6": 'm', "66": 'n', "666": 'o', "7": 'p', "77": 'q',
        "777": 'r', "7777": 's', "8": 't', "88": 'u', "888": 'v', "9": 'w', "99": 'x', "999": 'y', "9999": 'z',
        "0": ' ', "00": '  ', "000": '   ', "*": '*', "**": '*', "***": '*', "#": '#', "##": '#', "###": '#'
    }

    def cond(n: str):
        if n[0] in {'7', '9'}:
            return wrap(n, 4)
        else:
            return wrap(n, 3)

    list_grouped_by_number = [''.join(g) for k, g in groupby(keys)]
    list_grouped_max_three_or_four_digits = [cond(n) for n in list_grouped_by_number]
    flattened_list_grouped_max_three_or_four_digits = [
        lst for sublist in list_grouped_max_three_or_four_digits for lst in sublist]
    number_list_to_string_list = [num_dict[n] for n in flattened_list_grouped_max_three_or_four_digits]

    return "".join(number_list_to_string_list)

James Uejio RP Team on May 8, 2020

@WD You are absolutely correct I can’t believe I didn’t think of that case. I think the correct solution would have been to have the * or # be a delimeter between letters, or if you want to solve the problem above, you don’t need to worry about that case. For people reading this, try it out where you have * or # in between letters!

@fergusmeiklejohn That solution works as well! Would definitely recommend putting comments for what each list comprehension is doing but otherwise great use of list comprehensions and higher order functions. Not sure where groupby is imported from though.

Ignat Domanov on July 8, 2020

I think I do not understand the problem. What are the exact rules for the numbers-to-letter conversion? For instance, what is the answer for the string “222”? How can we distinguish between “aaa”, “ab”, “ba”, and “c”?

James Uejio RP Team on July 11, 2020

Hi Ignat yea that was my mistake, I didn’t think of that case. You can see the comment above to see some potential variants of the problem that are more realistic.

Eron on Aug. 8, 2020

Hi everyone, let’s try with re

from collections import defaultdict
import re

keys_map = defaultdict(tuple, {
  '1': ('',),
  '2': tuple('abc'),
  '3': tuple('def'),
  '4': tuple('ghi'),
  '5': tuple('jkl'),
  '6': tuple('mno'),
  '7': tuple('pqrs'),
  '8': tuple('tuv'),
  '9': tuple('wxyz'),
  '*': tuple('*'),
  '0': tuple(' '),
  '#': tuple('#')
})

def keypad_string(keys):
  reg = re.compile(r"(\d)\1*")
  string = ''
  matches = reg.finditer(keys)
  for match in matches:
    characters = keys_map.get(match.group(1))
    length_of_match = len(match.group(0))
    length_of_chars = len(characters)
    floor = length_of_match - length_of_chars
    while floor >= 0:
      literal = find_literal(length_of_chars, characters)
      string += literal
      floor = floor - length_of_chars
    if length_of_match % length_of_chars != 0:
      string += characters[length_of_match % length_of_chars - 1]
  return string

def find_literal(count_of_repeat, characters):
  length = len(characters)
  if length > 0:
    floor = count_of_repeat % length
    if floor == 0:
      return characters[length - 1]
    else:
      return characters[floor - 1]
  else:
    return ''

Özgür Gündoğan on Sept. 13, 2020

I think the solution in the video has some bugs.

First of all, you are passing by when key is 1. Think about the case "2212". The correct answer is 'ba', but your function probably returns 'c'.

Secondly, at the end the you don’t count the repeating keys. Think about the case "2122222". The correct answer is 'acb', but your function probably gets index out of range error because the count is 5 at the end.

James Uejio RP Team on Sept. 17, 2020

Hi Ozgur thank you for your comment. If you scroll up you will see my response to this.

Mohamed Guirat on Oct. 4, 2020

Here my suggestion before watching the solution:

from collections import defaultdict
import string

def keypad_string(keys):
    '''
    >>> keypad_string("12345")
    'adgj'
    >>> keypad_string("2022")
    'a b'
    >>> keypad_string("")
    ''
    >>> keypad_string("111")
    ''

    :param keys:
    :return:
    '''

    phone_digits = defaultdict(list)
    possible_letters =[l for l in string.ascii_lowercase]
    phone_digits[0]=[' ']
    phone_digits[1]=['']
    for i in range(2,10):
        if i == 7 or i == 9:
            phone_digits[i].extend(possible_letters[:4])
            possible_letters = possible_letters[4:]
        else:
            phone_digits[i].extend(possible_letters[:3])
            possible_letters=possible_letters[3:]
    phone_digits=dict(phone_digits)

    # phone_digits = {
    #     0: [' '],
    #     1: [''],
    #     2: ['a', 'b', 'c'],
    #     3: ['d', 'e', 'f'],
    #     4: ['g', 'h', 'i'],
    #     5: ['j', 'k', 'l'],
    #     6: ['m', 'n', 'o'],
    #     7: ['p', 'q', 'r', 's'],
    #     8: ['t', 'u', 'v'],
    #     9: ['w', 'x', 'y', 'z']
    # }
    letterDigits = defaultdict(str)
    for k, v in phone_digits.items():
        for letter in v:
            letterDigits[str(k)*(v.index(letter)+1)]=letter
    occ = 1
    result = ""
    for i, c in enumerate(keys):
        if i == len(keys)-1 or keys[i+1] != c:
            result += letterDigits[c*occ]
            occ=1
        else:
            occ+=1
    return result

jeffmallozzi on Oct. 8, 2020

Since ‘1’ is ignored, maybe that could be used to break up a sequence of multiple presses. For example to get ‘nn’ someone could press ‘66166’. Anther option is to use a space in the input string to represent the pause between multiple presses of a key that was usually used IRL on the old school feature phones when text messages were still new.

Here’s my solution, mostly from before watching the video. I added both options for using ‘1’ and ’ ’ to separate letters after reading the comments.

from itertools import groupby
def keypad_string(keys):
    '''
    Given a string consiting of 0-9,
    find the string that is created using
    a standard phone keypad
    |1        | 2 (abc) | 3 (def)  |
    |4 (ghi)  | 5 (jkl) | 6 (mno)  |
    |7 (pqrs) | 8 (tuv) | 9 (wxyz) |
    |    *    | 0 ( )   |    #     |
    You can ignore 1, and 0 corresponds to space
    >>> keypad_string('12345')
    'adgj'
    >>> keypad_string('4433555555666')
    'hello'
    >>> keypad_string('2022')
    'a b'
    >>> keypad_string('')
    ''
    >>> keypad_string('111')
    ''
    >>> keypad_string('221221221')
    'bbb'
    >>> keypad_string('22 22 22')
    'bbb'
    '''

    keypad = {
        '1': [''],
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z'],
        '*': [],
        '0': [' '],
        '#': []
    }

    if keys == '':
        return ''

    key_groups = []
    gropper = groupby(keys)
    for k, g in gropper:
        key_groups.append((k,len(list(g))))

    result = ''
    for key_group in key_groups:
        key, num = key_group
        if key == ' ':
            continue
        if num > len(keypad.get(key)):
            presses = num//len(keypad.get(key))
            remainder = num%len(keypad.get(key))
            for i in range(presses):
                result += keypad.get(key)[-1]
            if remainder:
                result += keypad.get(key)[remainder-1]
        else:
            result += keypad.get(key)[num-1]

    return result

jeffmallozzi on Oct. 8, 2020

A couple of edits from my first post: Added a ’ ’ virtual key to the key pad, this allowed me to remove the ‘if key == ’ ‘: continue Removed a for loop by just using string multiplication

from itertools import groupby
def keypad_string(keys):
    '''
    Given a string consisting of 0-9,
    find the string that is created using
    a standard phone keypad
    |1        | 2 (abc) | 3 (def)  |
    |4 (ghi)  | 5 (jkl) | 6 (mno)  |
    |7 (pqrs) | 8 (tuv) | 9 (wxyz) |
    |    *    | 0 ( )   |    #     |
    You can ignore 1, and 0 corresponds to space
    >>> keypad_string('12345')
    'adgj'
    >>> keypad_string('4433555555666')
    'hello'
    >>> keypad_string('2022')
    'a b'
    >>> keypad_string('')
    ''
    >>> keypad_string('111')
    ''
    >>> keypad_string('221221221')
    'bbb'
    >>> keypad_string('22 22 22')
    'bbb'
    >>> keypad_string('22222222222')
    'cccb'
    '''

    keypad = {
        '1': [''],
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z'],
        '*': [],
        '0': [' '],
        '#': [],
        ' ': ['']
    }

    if keys == '':
        return ''

    key_groups = []
    gropper = groupby(keys)
    for k, g in gropper:
        key_groups.append((k,len(list(g))))

    result = ''
    for key_group in key_groups:
        key, num = key_group
        if num > len(keypad.get(key)):
            presses = num//len(keypad.get(key))
            remainder = num%len(keypad.get(key))
            result += keypad.get(key)[-1]*presses
            if remainder:
                result += keypad.get(key)[remainder-1]
        else:
            result += keypad.get(key)[num-1]

    return result

Jon Scott on Nov. 12, 2020

Solution before watching the video:

def keypad_string(code:str) -> str:
    '''
    Given a string consisting of 0-9, 
    find the string that is created using
    a standard phone keypad
    |  1        |  2  (abc)  |  3 (def)    |
    |  4 (ghi)  |  5  (jkl)  |  6 (mno)    |
    |  7 (pqrs) |  8  (tuv)  |  9 (wxyz)   |
    |     *     |  0  ( )    |      #      |
    we can ignore 1, and 0 corresponds to space
    >>> keypad_string("12345")
    'adgj'
    >>> keypad_string("4433555555666")
    'hello'
    >>> keypad_string("2022")
    'a b'
    >>> keypad_string("")
    ''
    >>> keypad_string("111")
    ''

    The following does not work properly !!! was shooting for (the) 'moon'
    >>> keypad_string("666666666")
    'ooo'

    But this works as expected (with bogus sep)
    >>> keypad_string("616661666166")
    'moon'
    '''
    from itertools import groupby
    groupings_of_nums = [list(g) for k, g in groupby(code)]
    message = ''
    for cluster in groupings_of_nums:
# break clusters up into groups of 3 chars via :
#         [lst[i:i + 3] for i in range(0, len(cluster), 3)]
        rep = [cluster[i:i + 3] for i in range(0, len(cluster), 3)]
        for r in rep:
            if cluster[0] == '2':
                message += 'abc'[len(r) - 1]
            if cluster[0] == '3':
                message += 'def'[len(r) - 1]
            if cluster[0] == '4':
                message += 'ghi'[len(r) - 1]
            if cluster[0] == '5':
                message += 'jkl'[len(r)-1]
            if cluster[0] == '6':
                message += 'mno'[len(r) - 1]
            if cluster[0] == '7':
                message += 'pqrs'[len(r) - 1]
            if cluster[0] == '8':
                message += 'tuv'[len(r) - 1]
            if cluster[0] == '9':
                message += 'wxyz'[len(r) - 1]
            if cluster[0] == '0':
                # REDUCE MORE THAN ONE 0 DOWN TO JUST ONE SPACE
                message += ' '
    return message

Jon Scott on Nov. 19, 2020

found error in previous post:

...
    for cluster in groupings_of_nums:
        if cluster[0] in ['7','9']:
            size_of_r = 4
        else: 
            size_of_r = 3
        rep = [cluster[i:i + size_of_r] for i in range(0, len(cluster), size_of_r)]
...

reebaabu on Dec. 19, 2020

I got this way optimised a bit after watching the video.

from rp_collections_counter import defaultdict

def keypad_string(keys):

    dict_keypad = {
        '2' : ['a','b','c'],
        '3' : ['d','e','f'],
        '4' : ['g','h','i'],
        '5':  ['j','k','l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r','s'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y','z'] }

    count = defaultdict(int)
    l1 = []
    if keys == "" :
        return ''
    for i,x  in enumerate(keys):
        num_letters = 3
        if x in {"7", "9"}:
            num_letters = 4
        if x == "0" :
            l1.append(' ')
        if int(x) in range(2,10):
            j = x
            count[j] +=1
            k = count[j]
            if i != len(keys) - 1 and keys[i + 1] != j:
                l1.append(dict_keypad[j][k - 1])
                count[j] = 0
            elif i == len(keys) - 1:
                l1.append(dict_keypad[j][k - 1])
                count[j] = 0
            elif k == num_letters:
                l1.append(dict_keypad[j][k - 1])
                count[j] = 0
    return(''.join(l1))

linus-g on June 4, 2021

Here is my solution from before watching the video. The benefit of this solution is that it is short and I think relatively easy to follow, but this comes at the cost of having to search through the string many times to find possible matches.

def keypad_string(keys):
    # create list with mapping from digit to letters
    mapping = [        
        (2, "abc"),
        (3, "def"),
        (4, "ghi"),
        (5, "jkl"),
        (6, "mno"),
        (7, "pqrs"),
        (8, "tuv"),
        (9, "wxyz"),
        (0, " "),
        (1, "")
    ]

    for key, letters in mapping:
        if key == 1:
            keys = keys.replace(str(key), letters)
        for times_pressed in range(len(letters), 0, -1):
            keys = keys.replace(str(key) * times_pressed, letters[times_pressed - 1])
    return keys

andr3yk on Aug. 15, 2021

Below is my solution:

Create a key_mapping dictionary with enumerate and list of strings
Create a list of key mappings to be looked up in key_mapping dictionary in sequential order. I look back if the previous key is pressed again and check the maximum presses in the key_mapping dictionary. (Accepted edge case based on the hello)
Create a final result based on the key_input_count, I guess I could do it straight in the original logic to save on another loop, but it was already getting tricky to read. :)

    [{'4': 2}, {'3': 2}, {'5': 3}, {'5': 3}, {'6': 3}]
    'hello'

    key_mapping = {str(i): k for i, k in enumerate([
        [' '], [''], 'abc', 'def', 'ghi', 'jkl',
        'mno', 'pqrs', 'tuv', 'wxyz'
        ])
    }
    result = ''
    key_input_count = []
    for position, number in enumerate(keys):
        if position == 0:
            key_input_count.append({number: 1})
        else:
            if key_input_count[-1].get(number):
                if key_input_count[-1].get(number) == len(key_mapping[number]):
                    key_input_count.append({number: 1})
                else:
                    key_input_count[-1][number] += 1
            else:
                key_input_count.append({number: 1})

    for keystrokes in key_input_count:
        for key, value in keystrokes.items():
            result = result + (key_mapping.get(key)[value - 1])
    return result

Hashim Jacobs on Oct. 19, 2021

This course has been great! Because strings are immutable and you’re essentially building a new string each time you append a new char to it, doesn’t this run at O(n^2)? If that’s the case, then appending to a list would make it run at O(n) because appending to the end of a list is constant. After you exit the loop, return ‘’.join(result). Please let me know if I’m mistaken.

douglast on Nov. 4, 2021

This is what I produced before watching the solution:

def keypad_string(keys):
    from itertools import groupby

    # map the array position to the expected return values
    keypad = [' ', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

    # Group each number pressed with a count
    taps = [(digit, len(list(idx))) for digit,idx in groupby(keys)]

    s = ''
    # Loop over each digit pressed and the count
    for digit, num in taps:
        # If not a valid digit, skip
        if not digit.isdigit(): continue
        # Get the maximum times a digit can be pressed, 6=3, whereas 7=4
        max_taps = len(keypad[int(digit)])
        if max_taps == 0: continue

        total_taps = num # Initialize and track our total number of taps
        # Most the time probably only one iteration, but if you entered 55555, then it would do it twice.
        # It is stepping by the max_taps, which is 3 or 4.
        for i in range(0, num, max_taps):
            num_taps = total_taps
            # If over the maximum taps available for that digit, then subtract from total_taps and use max_taps
            if total_taps > max_taps:
                num_taps = max_taps
                total_taps -= num_taps
            # Get the correct letter from the mapped keypad
            s += keypad[int(digit)][num_taps-1]

    return s

print(keypad_string('12345'))
print(keypad_string('4433555555666'))
print(keypad_string('2022'))
print(keypad_string(''))
print(keypad_string('111'))
print(keypad_string('22#28'))

This allowed me to use something like a # character to do two characters and then one character, instead of it forcing to pull the third character. So, 22#28 returns 'bat' instead of 'ct'. I would love to hear any feedback on why this may or may not be a good way to approach this.

I did need to google itertools.groupby(), because I wasn’t sure how to use it. Do you know if on the interviews they allow you to google information, or is it strictly your in-memory knowledge?

Bartosz Zaczyński RP Team on Nov. 5, 2021

@douglast Whether you can use Google or not during a job interview depends on who will be interviewing you. I’ve been in both situations. At one time, a third-party recruiting company was handling the pre-screening through an online tool, which didn’t even allow me to use copy and paste for my coding challenge. The first time I tried that, it gave me a final warning and threatened to fail the test. However, in a different company, the interviewers were okay with searching for information online, so it really boils down to who you’ll be dealing with.

dilnahema on Dec. 11, 2021

This is the solution I came up with before watching the solution. It works for all the cases mentioned in the video. But not sure if I missed any corner case:

def keypad_string(keys):

    result = []
    word = []
    keypad = {
        "1" : [""],
        "2" : ["a", "b", "c"],
        "3" : ["d", "e", "f"],
        "4" : ["g", "h", "i"],
        "5" : ["j", "k", "l"],
        "6" : ["m", "n", "o"],
        "7" : ["p", "q", "r", "s"],
        "8" : ["t", "u", "v"],
        "9" : ["w", "x", "y", "z"],
        "0" : [" "],
        }
    keypad = build_keypad()

    for i, val in enumerate(keys):
        word.append(val)
        if i==len(keys)-1 or val != keys[i+1] or len(word) == len(keypad.get(val)):
            result.append(keypad.get(val)[len(word) - 1])
            word = []
    return ''.join(result)

For keypad generation:

def build_keypad():
    import string
    possible_letters = list(string.ascii_lowercase)
    keypad = {}
    keypad["0"] = [" "]
    keypad["1"] = [""]

    w = 0
    for i in range(2, 10):
        if i in {7, 9}:
            keypad[str(i)] = possible_letters[w:w+4]
            w += 4
        else:
            keypad[str(i)] = possible_letters[w:w+3]
            w += 3
    return keypad

Can I have a feedback on this solution?

alvarmaciel on Dec. 12, 2021

Hi, It take more than 45’ but this was my solution before watch the video.

def keypad_string(keys):
    """
    Given a string consisting of 0-9,
    find the string that is created using
    a standard phone keypad
    | 1        | 2 (abc) | 3 (def)  |
    | 4 (ghi)  | 5 (jkl) | 6 (mno)  |
    | 7 (pqrs) | 8 (tuv) | 9 (wxyz) |
    |     *    | 0 ( )   |     #    |
    You can ignore 1, and 0 corresponds to space
    >>> keypad_string("4433555555666")
    'hello'
    >>> keypad_string("2022")
    'a b'
    >>> keypad_string("")
    ''
    >>> keypad_string("111")
    ''
    >>> keypad_string("2222")
    'ca'
    >>> keypad_string("12345")
    'adgj'
    """

    map_dic = {
        "1": "",
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
        "0": " ",
        "*": "",
        "#": "",
    }

    def return_letter_3(key_pressed, i):
        if keys.count(key_pressed, i, i + 3) == 3:
            letter = map_dic[key_pressed][2:3]
            i += 3
        elif keys.count(key_pressed, i, i + 2) == 2:
            letter = map_dic[key_pressed][1:2]
            i += 2
        elif keys.count(key_pressed, i, i + 1) == 1:
            letter = map_dic[key_pressed][0:1]
            i += 1
        return letter, i

    def return_letter_4(key_pressed, i):
        if keys.count(key_pressed, i, i + 4) == 4:
            letter = map_dic[key_pressed][3:4]
            i += 4
        elif keys.count(key_pressed, i, i + 3) == 3:
            letter = map_dic[key_pressed][2:3]
            i += 3
        elif keys.count(key_pressed, i, i + 2) == 2:
            letter = map_dic[key_pressed][1:2]
            i += 2
        elif keys.count(key_pressed, i, i + 1) == 1:
            letter = map_dic[key_pressed][0:1]
            i += 1
        return letter, i

    enum_keys = enumerate(keys)
    decoded_string = ""
    letter = ""
    i = 0
    while i != len(keys):
        # breakpoint()
        if keys[i] == "2":
            letter, i = return_letter_3(keys[i], i)
        elif keys[i] == "3":
            letter, i = return_letter_3(keys[i], i)
        elif keys[i] == "4":
            letter, i = return_letter_3(keys[i], i)
        elif keys[i] == "5":
            letter, i = return_letter_3(keys[i], i)
        elif keys[i] == "6":
            letter, i = return_letter_3(keys[i], i)
        elif keys[i] == "8":
            letter, i = return_letter_3(keys[i], i)
        elif keys[i] == "7":
            letter, i = return_letter_4(keys[i], i)
        elif keys[i] == "8":
            letter, i = return_letter_4(keys[i], i)
        elif keys[i] == "0":
            letter = " "
            i += 1
        else:
            i += 1

        decoded_string += letter

    return decoded_string

cuzor on Jan. 31, 2022

def keypad_strings(keys):
    numbers_dict = defaultdict()
    char = 97
    for _ in range(10):
        if _ == 7 or _ == 9:
            key = 4
            numbers_dict[_] = (char, key)
            char += key
        elif _ == 0 or _ == 1:
            numbers_dict[_] = (0, 0)
        else:
            key = 3
            numbers_dict[_] = (char, key)
            char += key
    counter = 0
    result = ''
    for i, key in enumerate(keys):
        if numbers_dict[int(key)][0] == 0:
            continue
        if i > 0 and key == keys[i - 1]:
            counter += 1
        else:
            counter = 0
        char_int = numbers_dict[int(key)][0] + counter
        if counter < numbers_dict[int(key)][1]:
            if counter == 0:
                result += chr(char_int)
            else:
                result = result[:-1] + chr(char_int)
        else:
            counter = 0
            result += chr(char_int)

    return result

James Carr on May 13, 2022

My solution using deque and the string module

from collections import deque
import string


def _map_keys() -> dict:
    """ Map keypad numbers to ascii characters

    Returns:
        dict: Maps key number to a list of characters
    """

    FOUR_CHARS = {7, 9}
    key_map = {'0': [" "], '1': []} # Hard code special keys
    start, stop = 0, 3 # Set the initial slice indexes

    def _inc_slice_index(n):
        """ Increment the start:stop slicing indexes by n """
        nonlocal start, stop
        start += n
        stop += n

    for i in range(len(key_map), len(string.digits)):
        key = str(i)
        if i in FOUR_CHARS:
            key_map[key] = list(string.ascii_lowercase[start:stop + 1])
            _inc_slice_index(4)
        else:
            key_map[key] = list(string.ascii_lowercase[start:stop])
            _inc_slice_index(3)

    return key_map


def _create_string(seq) -> str:
    """ Create a string from a list of integers. The integer maps to a 
    possible list of chars.  The frequency (length of sequence) determines
    the index of the character to use.  
    For example: [4, 4, 4], length 3, maps
    to the character 'i'; the 3rd character in the list.

    Args:
        sequence (list[[str]]): Eg: ['2','2'],['0'], ['2']]

    Returns:
        str: A string from the sequence of key presses.
    """

    # Get a key mapping.
    keymap = _map_keys()

    # Build the string from the key press sequence.
    str_seq = ""
    for freq in seq:
        str_seq += keymap[freq[0]][len(freq) - 1]
    return str_seq


def keypad_string(keys):
    '''
    Given a string consisting of 0-9,
    find the string that is created using
    a standard phone keypad
    | 1        | 2 (abc) | 3 (def)  |
    | 4 (ghi)  | 5 (jkl) | 6 (mno)  |
    | 7 (pqrs) | 8 (tuv) | 9 (wxyz) |
    |     *    | 0 ( )   |     #    |
    You can ignore 1, and 0 corresponds to space
    >>> keypad_string("12345")
    'adgj'
    >>> keypad_string("4433555555666")
    'hello'
    >>> keypad_string("2022")
    'a b'
    >>> keypad_string("")
    ''
    >>> keypad_string("111")
    ''
    >>> keypad_string("#")
    Traceback (most recent call last):
    AssertionError: Invalid Key: Acceptable keys 0123456789
    '''

    MAX_KEYPRESS_COUNT = 3  # Max number of times a key can be pressed
    IGNORE_KEYS = {'1'}     # Set of keys that do nothing and will be ignored.

    if not keys:
        return ''

    keys_q = deque(keys)
    seq, buf, count = [], [], 0

    while(keys_q):
        key_pressed = keys_q.popleft()  # popleft=O(1) vs pop(0)=O(n)
        assert key_pressed in string.digits, "Invalid Key: Acceptable keys " + string.digits

        # Ignore certain keys, and service the next key press
        if key_pressed in IGNORE_KEYS: continue

        count += 1
        # Append the pressed key to the buffer.  If the key has been pressed 3 times, the max
        # sequence has been reached, and must be appened to the sequence list.
        if (not buf or buf and key_pressed == buf[0]) and count < MAX_KEYPRESS_COUNT:
            buf.append(key_pressed)
        else:
            seq.append(buf)
            buf = []
            buf.append(key_pressed)
            count = 0

    # Append the buffer if it contains valid key presses.
    if buf: seq.append(buf)
    return _create_string(seq)

abdrfaoui on Oct. 24, 2022

My solution:

def keypad_string(keys):
        '''
        Given a string consisting of 0-9,
        find the string that is created using
        a standard phone keypad
        | 1        | 2 (abc) | 3 (def)  |
        | 4 (ghi)  | 5 (jkl) | 6 (mno)  |
        | 7 (pqrs) | 8 (tuv) | 9 (wxyz) |
        |     *    | 0 ( )   |     #    |
        You can ignore 1, and 0 corresponds to space
        >>> keypad_string("12345")
        'adgj'
        >>> keypad_string("4433555555666")
        'hello'
        >>> keypad_string("2022")
        'a b'
        >>> keypad_string("")
        ''
        >>> keypad_string("111")
        ''
        '''
        mydict = []
        mystr = ''
        res = ''
        for c in keys:
            if (c in mystr) or mystr == "":
                mystr += c
            else:
                mydict.append(mystr)
                mystr = c
        mydict.append(mystr)
        for c in mydict:
            #print(f"{c} {len(c)}")
            if '0' in c:
                res += " "*len(c)
            if '1' in c or '*' in c or '#' in c:
                continue
            if '2' in c:
                r = len(c) % 3
                q = len(c) // 3
                res += 'c'*q
                if r == 1:
                    res += 'a'
                if r == 2:
                    res += 'b'
            if '3' in c:
                r = len(c) % 3
                q = len(c) // 3
                res += 'f'*q
                if r == 1:
                    res += 'd'
                if r == 2:
                    res += 'e'
            if '4' in c:
                r = len(c) % 3
                q = len(c) // 3
                res += 'i'*q
                if r == 1:
                    res += 'g'
                if r == 2:
                    res += 'h'
            if '5' in c:
                r = len(c) % 3
                q = len(c) // 3
                res += 'l'*q
                if r == 1:
                    res += 'j'
                if r == 2:
                    res += 'k'
            if '6' in c:
                r = len(c) % 3
                q = len(c) // 3
                res += 'o'*q
                if r == 1:
                    res += 'm'
                if r == 2:
                    res += 'n'
            if '7' in c:
                r = len(c) % 4
                q = len(c) // 4
                res += 's'*q
                if r == 1:
                    res += 'p'
                if r == 2:
                    res += 'q'
                if r == 3:
                    res += 'r'
            if '8' in c:
                r = len(c) % 3
                q = len(c) // 3
                res += 'v'*q
                if r == 1:
                    res += 't'
                if r == 2:
                    res += 'u'
            if '9' in c:
                r = len(c) % 4
                q = len(c) // 4
                res += 'z'*q
                if r == 1:
                    res += 'w'
                if r == 2:
                    res += 'x'
                if r == 3:
                    res += 'y'
        return res

marcinbar on Jan. 15, 2023

@James Nice course, but your solution and anyone else from discussion doesn’t work for some cases.

Failed example: keypad_string(‘4444777555’) Expected: ‘girl’ Got: ‘igrl’

Failed example: keypad_string(“266662”) Expected: ‘anna’ Got: ‘aoma’

Failed example: keypad_string(“77772666620444555336637777”) Expected: ‘samoa ilands’ Got: ‘saoma ilends’

In my opinion, this kind of translation will only work if during entering numbers, for letters from the same button, will be separated by a time break, which will suggest to the program that the next same numbers are another letter from the same button. Otherwise, the program will not be able to determine if the sequence 6666 means ‘om’ or ‘mo’ or maybe ‘nn’.

mattshirley on Dec. 5, 2023

This is my full solution utilizing the itertools.groupby function (this function could be reimplemented from scratch during an interview fairly easily if needed).

A couple points:

I strongly recommend updating this video to explicitly state the limitation that the solution makes it impossible to distinguish repeated letters from the same grouping. i.e. it is impossible to detect the message 'jk' because keypad_string("555") will output the string 'l'. This is particularly important given this is a tutorial is for programmers still learning who might not be able to easily detect whether this is actually a limitation given the instructions, leading to confusion. You can partly work around this limitation by using 0 as a delimiter. i.e. keypad_string("5055") produces 'j k'.
I think it is much better to hardcode a dictionary in this scenario. The helper function is still 100% deterministic (i.e. you get no flexibility over hardcoding), and merely hides business logic that will be harder for someone to identify in the future. It’s also likely shorter than a function used to do the same thing.

from itertools import groupby
import string


KEYPAD_MAP: dict[str, list[str]] = {
    "2": list("abc"),
    "3": list("def"),
    "4": list("ghi"),
    "5": list("jkl"),
    "6": list("mno"),
    "7": list("pqrs"),
    "8": list("tuv"),
    "9": list("wxyz"),
    "0": [" "],
}

DIGIT_SET = set(string.digits)


def keypad_string(keys: str) -> str:
    """
    Given a string consisting of 0-9,
    find the string that is created using
    a standard phone keypad
    | 1        | 2 (abc) | 3 (def)  |
    | 4 (ghi)  | 5 (jkl) | 6 (mno)  |
    | 7 (pqrs) | 8 (tuv) | 9 (wxyz) |
    |     *    | 0 ( )   |     #    |
    You can ignore 1, and 0 corresponds to space

    >>> keypad_string("12345")
    'adgj'
    >>> keypad_string("4433555555666")
    'hello'
    >>> keypad_string("2022")
    'a b'
    >>> keypad_string("")
    ''
    >>> keypad_string("111")
    ''
    >>> keypad_string("9442877770887")
    'whats up'
    >>> keypad_string("555")
    'l'
    >>> keypad_string("000")
    '   '
    >>> keypad_string("0000a")
    Traceback (most recent call last):
    AssertionError: Input must be a digit: a
    >>> keypad_string("5055")
    'j k'
    """
    if keys == "":
        return ""
    for char in keys:
        assert char in DIGIT_SET, f"Input must be a digit: {char}"

    grouped = [list(group) for char, group in groupby(keys)]  # O(n)
    # breakpoint()

    output = list()

    for key_pattern in grouped:
        digit = key_pattern[0]

        # special case for 1
        if digit == "1":
            continue
        remaining_length = len(key_pattern)

        characters = KEYPAD_MAP[digit]

        # determine how many characters are actually produced by group
        while remaining_length > len(characters):
            # if more keys pressed than characters, this means there must be multiple letters
            # grab the last character, decrement the length, and continue
            output.append(characters[-1])
            remaining_length -= len(characters)

        if remaining_length > 0:
            output.append(characters[remaining_length - 1])

    return "".join(output)

AJT Boekhorst on Dec. 15, 2023

Feel like I’ve chosen a different approach, which I’d also like to share. I split up the string to a list of string [‘444’, ‘33’, ‘2’] of which I use the first digit and length to determin the letter.

Hope it helps:

def keypad_string(keys):
    word = ''
    grid = " ,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz".split(',')

    # Create comme separated string
    newstr = ''
    for i, k in enumerate(keys):
      if(i == 0 or k != keys[i-1]):
        newstr += ','
      newstr += k

    for gr in newstr[1:].split(','):
      if(len(gr)>0 and gr[0] in '023456789'):
          key, count = int(gr[0]), len(gr)
          max = len(grid[key])
          remain = count % max
          word = word + count // max * grid[key][max-1]
          if( remain > 0):
            word = word + grid[key][remain-1]

    return word

Francis Obiagwu on Jan. 4, 2024

def keypad_string(keys):
    '''
    Given a string consisting of 0-9,
    find the string that is created using
    a standard phone keypad
    | 1         | 2 (abc) | 3 (def)  |
    | 4 (ghi)   | 5 (jkl) | 6 (mno)  |
    | 7 (pqrs)  | 8 (tuv) | 9 (wxyz) |
    | *         | 0 ( )   | #        |
    You can ignore 1, and 0 corresponds to space
    >>> keypad_string("12345")
    'adgj'
    >>> keypad_string("4433555555666")
    'hello'
    '''

    KEY_MAPPING = {"1": "",
                   "2": "abc",
                   "3": "def",
                   "4": "ghi",
                   "5": "jkl",
                   "6": "mno",
                   "7": "pqrs",
                   "8": "tuv",
                   "9": "wxyz",
                   "0": " "}

    final_str = ""
    def str_builder(digit, count):
        str_builder = ""
        mapped_chars_list = list(KEY_MAPPING[digit]) # 9 ["w", "x", "y", "z"]
        size_of_mapping = len(KEY_MAPPING[digit]) # 4
        remainder = count%size_of_mapping
        rounds = count//size_of_mapping
        if rounds > 0:
            for _ in range(rounds):
                str_builder += mapped_chars_list[size_of_mapping - 1] 
            if remainder > 0:
                str_builder += mapped_chars_list[remainder - 1] 
        else: 
            str_builder += mapped_chars_list[count - 1] 

        return str_builder

    left = right = 0
    while right < len(keys):
        key = keys[left]
        if key == "1" or key == "0":
            final_str += KEY_MAPPING[key]
            left +=1
            right +=1
        else:
            key_count = 0
            while right < len(keys):
                if key == keys[right]:
                    key_count += 1
                else:
                    left = right
                    break
                right +=1


            final_str += str_builder(key, key_count)

    return final_str

Become a Member to join the conversation.