Convert a Sentence into its equivalent mobile numeric keypad sequence

Problem Statement

Given a sentence, convert it to its equivalent mobile numeric keypad sequence. Each character should be mapped to the key presses required on a traditional phone keypad.

Keypad Mapping:

Example:

• Input: "HELLO WORLD"
• Output: "4433555555666096teleiff6755553"
• Explanation:
  • H → 44 (press 4 twice)
  • E → 33 (press 3 twice)
  • L → 555 (press 5 three times)
  • L → 555
  • O → 666 (press 6 three times)
  • (space) → 0
  • W → 9 (press 9 once)
  • ... and so on

Keypad Mapping Table

| Key | Characters | Sequence | |-----|------------|----------| | 2 | A, B, C | 2, 22, 222 | | 3 | D, E, F | 3, 33, 333 | | 4 | G, H, I | 4, 44, 444 | | 5 | J, K, L | 5, 55, 555 | | 6 | M, N, O | 6, 66, 666 | | 7 | P, Q, R, S | 7, 77, 777, 7777 | | 8 | T, U, V | 8, 88, 888 | | 9 | W, X, Y, Z | 9, 99, 999, 9999 | | 0 | Space | 0 |

Approach 1: Using Mapping Array

Intuition

Create a mapping array where each index corresponds to a character, and the value is the keypad sequence.

Algorithm

1. Create mapping for all 26 characters + space
2. For each character in input, look up its sequence
3. Concatenate all sequences

public class Solution {
    public String convertToKeypad(String sentence) {
        String[] keyMap = {
            "2", "22", "222",           // ABC
            "3", "33", "333",           // DEF
            "4", "44", "444",           // GHI
            "5", "55", "555",           // JKL
            "6", "66", "666",           // MNO
            "7", "77", "777", "7777",   // PQRS
            "8", "88", "888",           // TUV
            "9", "99", "999", "9999"    // WXYZ
        };
        
        StringBuilder result = new StringBuilder();
        sentence = sentence.toUpperCase();
        
        for (char c : sentence.toCharArray()) {
            if (c == ' ') {
                result.append("0");
            } else if (c >= 'A' && c <= 'Z') {
                result.append(keyMap[c - 'A']);
            }
        }
        
        return result.toString();
    }
}

Complexity Analysis

• Time Complexity: O(n) - Process each character once
• Space Complexity: O(n) - For output string (O(1) auxiliary space)

Approach 2: Mathematical Calculation

Intuition

Calculate the key and position mathematically based on character code.

public class Solution {
    public String convertToKeypad(String sentence) {
        StringBuilder result = new StringBuilder();
        sentence = sentence.toUpperCase();
        
        for (char c : sentence.toCharArray()) {
            if (c == ' ') {
                result.append("0");
                continue;
            }
            
            if (c < 'A' || c > 'Z') continue;
            
            int pos = c - 'A';
            int key, presses;
            
            if (pos < 15) {  // A-O
                key = 2 + pos / 3;
                presses = 1 + pos % 3;
            } else if (pos < 19) {  // P-S
                key = 7;
                presses = 1 + pos - 15;
            } else if (pos < 22) {  // T-V
                key = 8;
                presses = 1 + pos - 19;
            } else {  // W-Z
                key = 9;
                presses = 1 + pos - 22;
            }
            
            for (int i = 0; i < presses; i++) {
                result.append(key);
            }
        }
        
        return result.toString();
    }
}

Approach 3: Reverse Conversion (Keypad to Text)

Intuition

Convert a keypad sequence back to text. Handle consecutive same digits.

Handling Numbers in Input

If input can contain digits too:

Key Takeaways

1. Direct mapping is simplest - use array or hash map
2. Mathematical approach avoids storing mapping but is more complex
3. Handle special cases: space, numbers, special characters
4. Keys 7 and 9 have 4 letters each, others have 3
5. This is a classic encoding/decoding problem
6. Consider lowercase/uppercase normalization
7. Real T9 dictionaries use word prediction, not just keypad encoding

Related Problems

1. T9 Dictionary - Predict words from keypad sequence
2. Letter Combinations of Phone Number (LeetCode 17)
3. Decode String - Similar encoding/decoding pattern