1. Runtime Distribution

2. Submission Details

3. Description

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

4. Example

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

5. Code

char map[][5] = {
    "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
};

char** letterCombinations(char* digits, int* returnSize) {
    int i = 0, resultLength = 1;

    while (digits[i] != '\0') {
        resultLength *= digits[i] == '7' || digits[i] == '9' ? 4 : 3;
        i++;
    }

    *returnSize = i == 0 ? 0 : resultLength;

    char ** result = (char**)malloc(sizeof(char*) *resultLength);

    for (int j = 0; j < resultLength; j++) {

        result[j] = (char*)malloc(sizeof(char)*i);

        int vary = j, k;

        for (k = 0; k < i; k++) {

            int p = digits[k] == '7' || digits[k] == '9' ? 4 : 3;

            result[j][k] = map[digits[k] - '2'][vary%p];

            vary = vary / p;
        }
        result[j][k] = '\0';
    }
    return result;
}

private static readonly string[] Mapping =
{
    "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};

public IList<string> LetterCombinations(string digits)
{
    if (digits.Length == 0)
    {
        return new List<string>();
    }

    Queue<string> result = new Queue<string>();
    result.Enqueue("");

    for (var i = 0; i < digits.Length; i++)
    {
        var index = digits[i] - '0';
        while (result.Peek().Length == i)
        {
            var prefix = result.Dequeue();
            foreach (var c in Mapping[index])
            {
                result.Enqueue(prefix + c);
            }
        }
    }
    return result.ToList();
}

6.Test

#include <stdio.h>
#include <stdlib.h>

char map[][5] = {
    "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
};

char** letterCombinations(char* digits, int* returnSize) {
    int i = 0, resultLength = 1;

    while (digits[i] != '\0') {
        resultLength *= digits[i] == '7' || digits[i] == '9' ? 4 : 3;
        i++;
    }

    *returnSize = i == 0 ? 0 : resultLength;

    char ** result = (char**)malloc(sizeof(char*) *resultLength);

    for (int j = 0; j < resultLength; j++) {

        result[j] = (char*)malloc(sizeof(char)*i);

        int vary = j, k;

        for (k = 0; k < i; k++) {

            int p = digits[k] == '7' || digits[k] == '9' ? 4 : 3;

            result[j][k] = map[digits[k] - '2'][vary%p];

            vary = vary / p;
        }
        result[j][k] = '\0';
    }
    return result;
}

int main() {
    char digits[3] = {'2','3','\0'};
    int * returnSize = malloc(sizeof(int));
    char ** result = letterCombinations(digits, returnSize);
    printf("%d\n", *returnSize);
    system("pause");
    return 0;
}

using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace Csharp.Queue
{
    [TestClass]
    public class LeetCode0017
    {
        private static readonly string[] Mapping =
        {
            "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        };

        public IList<string> LetterCombinations(string digits)
        {
            if (digits.Length == 0)
            {
                return new List<string>();
            }

            Queue<string> result = new Queue<string>();
            result.Enqueue("");

            for (var i = 0; i < digits.Length; i++)
            {
                var index = digits[i] - '0';
                while (result.Peek().Length == i)
                {
                    var prefix = result.Dequeue();
                    foreach (var c in Mapping[index])
                    {
                        result.Enqueue(prefix + c);
                    }
                }
            }
            return result.ToList();
        }

        [TestMethod]
        public void Test()
        {
            var digital = "23";
            IList<string> result = LetterCombinations(digital);
            foreach (var str in result)
            {
                Console.WriteLine(str);
            }
        }
    }
}