[Google Question][LeetCode] Letter Combinations of a Phone Number

Problem: Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Input: digits = ""
Output: []

Input: digits = "2"
Output: ["a","b","c"]

Approach: Nothing to explain here. We are just going to use backtracking here. Just look at the implementation to understand it in detail.

Implementation in C#:

        public IList<string> LetterCombinations(string digits)

    {

        var mapping = this.GenerateLetterMapping();

        int length = digits?.Length ?? 0;

        if (length == 0 || (length == 1

            && !mapping.ContainsKey(digits[0])))

        {

            return new List<string>();

        }

        List<string> result = new List<string>();

        var currCombination = new StringBuilder();

        this.GetLetterCombinations(digits,

                                   0,

                                   currCombination,

                                   mapping,

                                   result);

        return result;

    }

    private void GetLetterCombinations(string digits,

                                       int currIndex,

                                       StringBuilder currCombination,

                                       Dictionary<char, List<char>> mapping,

                                       List<string> result)

    {

        if (currIndex == digits.Length)

        {

            if (currCombination.Length > 0)

            {

                result.Add(currCombination.ToString());

                return;

            }

        }

        if (mapping.ContainsKey(digits[currIndex]))

        {

            foreach(char ch in mapping[digits[currIndex]])

            {

                currCombination.Append(ch);

                this.GetLetterCombinations(digits,

                                           currIndex + 1,

                                           currCombination,

                                           mapping,

                                           result);

                --currCombination.Length;

            }

        }

    }

    private Dictionary<char, List<char>> GenerateLetterMapping()

    {

        var mapping = new Dictionary<char, List<char>>();

        mapping['2'] = new List<char> {'a', 'b', 'c'};

        mapping['3'] = new List<char> {'d', 'e', 'f'};

        mapping['4'] = new List<char> {'g', 'h', 'i'};

        mapping['5'] = new List<char> {'j', 'k', 'l'};

        mapping['6'] = new List<char> {'m', 'n', 'o'};

        mapping['7'] = new List<char> {'p', 'q', 'r', 's'};

        mapping['8'] = new List<char> {'t', 'u', 'v'};

        mapping['9'] = new List<char> {'w', 'x', 'y', 'z'};

        return mapping;

    }

Complexity: O(3^m * 4 ^n) where m is the number of digits which are mapped to 3 characters and n is the number of digits which are mapped to 4 characters. At worst case it will be O(4^n).