Convert a Sentence into its equivalent mobile numeric keypad sequence

The problem, simply

Old phones had number keys with letters printed on them. Key 2 has A B C, key 3 has D E F, and so on up to key 9 with W X Y Z. Key 0 is the space.

To type a letter you press its key once for the first letter on it, twice for the second, and so on. Given a sentence in capital letters and spaces, give back the string of key presses.

A story to remember it

Picture it

Examples

Way 1: the simple way

For every letter, hunt over the keypad: look at each key's letters until you find it. Its spot on the key tells you how many presses.

1. Keep the eight key labels: ABC, DEF, ..., WXYZ.
2. For each letter, try keys 2 to 9. When the label contains the letter at spot p, press that key p + 1 times.
3. A space adds 0.

class Solution {
    public String toKeypad(String s) {
        String[] keys = {"", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"};
        StringBuilder out = new StringBuilder();
        for (char c : s.toUpperCase().toCharArray()) {
            if (c == ' ') { out.append('0'); continue; }
            for (int k = 2; k <= 9; k++) {                 // hunt over the keypad
                int p = keys[k].indexOf(c);
                if (p >= 0) {
                    for (int t = 0; t <= p; t++) out.append(k);   // press p + 1 times
                    break;
                }
            }
        }
        return out.toString();
    }
}

How long it takes: for each of the n letters we may scan all k = 26 letters on the keypad, O(n * k). Extra room besides the answer: O(1).

Way 2: the clever way

Make the cheat sheet first: a table with one entry per letter, A to Z, holding its presses. Then each letter is one look up by its position in the alphabet, c - 'A'.

1. Build the table code[0..25]: 2, 22, 222, 3, 33, ..., 9999.
2. For each character: space adds 0, a letter adds code[c - 'A'].

class Solution {
    // the cheat sheet: presses for A, B, C, ..., Z
    private static final String[] CODE = {
        "2", "22", "222",            // A B C
        "3", "33", "333",            // D E F
        "4", "44", "444",            // G H I
        "5", "55", "555",            // J K L
        "6", "66", "666",            // M N O
        "7", "77", "777", "7777",    // P Q R S
        "8", "88", "888",            // T U V
        "9", "99", "999", "9999"     // W X Y Z
    };

    public String toKeypad(String s) {
        StringBuilder out = new StringBuilder();
        for (char c : s.toUpperCase().toCharArray()) {
            if (c == ' ') out.append('0');
            else if (c >= 'A' && c <= 'Z') out.append(CODE[c - 'A']);   // one look up
        }
        return out.toString();
    }
}

How long it takes: one look up per character, and each adds at most 4 presses, so O(n). Extra room besides the answer: the table has 26 entries no matter how long the sentence is, O(1).

Watch out for

• Lowercase input: turn it into capitals first, or c - 'A' goes out of range.
• Characters that are not letters or spaces: decide with the interviewer. Skipping them is common.
• Build the answer with a StringBuilder. Adding to a String in a loop copies it every time.

What interviewers ask next

• Can you decode the presses back to text? Not always. 44444 could be HI (44 444) or IH (444 44), or GGGGG. Real phones used a pause between letters for this reason. Ask for a separator, then split and look up.
• All words a digit string could spell, one letter per digit? That is "letter combinations of a phone number": backtracking over the letters of each digit, O(4^n) results in the worst case.
• Predictive typing (T9): map each dictionary word to its digit string once, and store words in a map or trie keyed by that digit string.
• What if the keypad layout is given as input? Build the cheat sheet from the layout first. The typing loop does not change.

Remember this

Grown-up words: the cheat sheet is a lookup table, finding a letter's spot by c - 'A' is direct indexing, and doing work ahead of time so later steps are fast is precomputation.