Letter Combinations of a Phone Number

1. Problem Description

Given a string containing only digits 2-9, return all letter combinations it can represent. The answer may be returned in any order.

The mapping from digits to letters is the same as on a telephone keypad. Note that 1 does not map to any letters.

2. Approach

• Permutation

3. Implementation

package main

import "sort"

var m = map[rune][]rune{
	'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'},
}

func LetterCombinations(digits string) []string {
	if digits == "" {
		return nil

	}
	digitsPerms := make([]string, 0)
	abc := make([]rune, len(digits), len(digits))
	digitsPermutation([]rune(digits), abc, 0, &digitsPerms)
	sort.Strings(digitsPerms)
	return digitsPerms
}

func digitsPermutation(digits []rune, abc []rune, index int, digitsPerms *[]string) {
	if index == len(digits) {
		*digitsPerms = append(*digitsPerms, string(abc))
		return
	}

    // The digits are ordered here, so there is no need to swap them for a full permutation
	currentNum := digits[index]
	for _, r := range m[currentNum] {
		abc[index] = r
		digitsPermutation(digits, abc, index+1, digitsPerms)
	}

}

4. References

• 17. Letter Combinations of a Phone Number - LeetCode