Letter Combinations of a Phone Number - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Letter Combinations of a Phone Number" Problem in Go

Difficulty: Medium | Tags: Hash Table, String, Backtracking

Introduction

This problem requires generating all possible letter combinations that a given string of digits (2-9) could represent, based on traditional telephone keypad mappings. It's a classic backtracking problem that tests recursion and combinatorial logic.

Problem Analysis

Given digits like "23", the output should include all combinations of letters mapped to 2 (a, b, c) and 3 (d, e, f). The challenge lies in efficiently exploring all possible combinations without repetition or missing any cases.

Solution Approach

We use a backtracking approach to build combinations incrementally. We start with an empty string and recursively append each possible letter for the current digit, then proceed to the next digit until all digits are processed.

Go Implementation


func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }
    digitToLetters := map[byte][]string{
        '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"},
    }
    var result []string
    backtrack(digits, 0, "", digitToLetters, &result)
    return result
}
func backtrack(digits string, index int, current string, digitToLetters map[byte][]string, result *[]string) {
    if index == len(digits) {
        *result = append(*result, current)
        return
    }
    digit := digits[index]
    letters := digitToLetters[digit]
    for _, letter := range letters {
        backtrack(digits, index+1, current+letter, digitToLetters, result)
    }
}

Complexity Analysis

Time Complexity: O(4^N), where N is the length of the input digits. In the worst case (digits like "7" or "9"), each digit maps to 4 letters, leading to 4^N combinations.

Space Complexity: O(N) for the recursion stack, where N is the length of the digits. The output space is O(4^N) to store all combinations.

Testing and Examples

Test cases:

  • Input: "23" → Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
  • Input: "" → Output: []
  • Input: "2" → Output: ["a","b","c"]

Best Practices and Tips

1. Use a map to store digit-to-letters mappings for quick lookup.

2. Handle the empty input case upfront to avoid unnecessary processing.

3. Prefer recursion for backtracking problems due to cleaner code and implicit stack management.

Read more